单调栈.md

• 单调栈总结
  • 每日温度 (medium)
  • 柱状图中最大的矩形 (hard)
  • 去除重复字母 (hard 贪心)

单调栈总结

每日温度

LeetCode中文

解法: 最基本的单调栈实现

class Solution {
public:
    vector<int> dailyTemperatures(const vector<int>& temperatures) {
        stack<pair<int, int>> sta;
        int n = temperatures.size();
        vector<int> res(n, 0);
        for (int i = n - 1; i >= 0; --i) {
            int cur = temperatures[i];
            while (!sta.empty() && cur >= sta.top().second) {
                sta.pop();
            }
            if (sta.empty()) res[i] = 0;
            else res[i] = sta.top().first - i;
            sta.push({i, cur});
        }
        return res;
    }
};

柱状图中最大的矩形

LeetCode中文

解法：利用单调栈，求出左边和右边最后一个>=当前元素的位置，然后重新遍历的时候，计算每个元素形成的最大巨星面积

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> sta, sta1;
        int len = heights.size();
        vector<int> left_mp(len), right_mp(len);
        for (int i = 0; i < len; ++i) {
            while (!sta.empty() && heights[i] <= heights[sta.top()]) {
                sta.pop();
            }
            if (sta.empty()) {
                left_mp[i] = 0;
            } else {
                left_mp[i] = sta.top() + 1;
            }
            sta.push(i);
        }
        for (int i = len - 1; i >= 0; --i) {
            while (!sta1.empty() && heights[i] <= heights[sta1.top()]) {
                sta1.pop();
            }
            if (sta1.empty()) {
                right_mp[i] = len - 1;
            } else {
                right_mp[i] = sta1.top() - 1;
            }
            sta1.push(i);
        }
        int res = 0;
        for (int i = 0; i < len; ++i) {
            res = max(res, (right_mp[i] - left_mp[i] + 1) * heights[i]);
        }
        return res;
    }
};