单调栈知识点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 输入 nums，返回每个元素右边第一个比它大的元素值，没有返回 -1
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;  // 存下标，不是值

    // 从后往前遍历
    for (int i = n - 1; i >= 0; i--) {
        // 栈顶比当前小，肯定不是答案，弹出
        while (!st.empty() && nums[st.top()] <= nums[i]) {
            st.pop();
        }
        // 此时栈顶就是右边第一个更大的
        if (!st.empty()) res[i] = nums[st.top()];
        st.push(i);
    }
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n, 0);
    stack<int> st;

    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && temperatures[st.top()] <= temperatures[i]) {
            st.pop();
        }
        if (!st.empty()) res[i] = st.top() - i;  // 存下标，算天数差
        st.push(i);
    }
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;

    for (int i = 2 * n - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= nums[i % n]) {
            st.pop();
        }
        if (i < n && !st.empty()) res[i] = st.top();
        st.push(nums[i % n]);
    }
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n, -1);   // 左边第一个更小的下标
    vector<int> right(n, n);   // 右边第一个更小的下标
    stack<int> st;

    // 找左边第一个更小
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            st.pop();
        }
        if (!st.empty()) left[i] = st.top();
        st.push(i);
    }

    // 清空栈，找右边第一个更小
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            st.pop();
        }
        if (!st.empty()) right[i] = st.top();
        st.push(i);
    }

    // 计算面积
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, heights[i] * (right[i] - left[i] - 1));
    }
    return ans;
}