单调栈

问题

了解数组中的一个数，左边最近的比这个数大的数，和右边最近的比这个数大的数在哪
在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景
单调栈
无重复数字
求某个数字附近最近的比他大的数字：
- 使用一个栈，这个栈从下到上是由大到小的顺序
- 新加入的数字符合单调性？直接加入
- 不符合单调性？弹出栈顶的数字，此时记录，对于被弹出的这个数字而言：
  - 左边最近的比他大的数字就是弹出这个数字之后的栈顶元素
  - 右边最近的比他大的数字就是正要进栈的数字
  - 直到符合单调性为止
- 最后结束的时候栈中还有数据怎么办？
  - 栈中剩余的所有数据的右边最近比他大的数字都是无
  - 左边最近的比他大的数字都是他在栈中的下一个元素
  - 栈底的最后一个元素左右都是无
    有重复数字
栈中放的内容都是链表，每个位置链表结点存放index
弹出的时候，右边最近比他大的数字是当前等待进栈的数字，左边最近的比他大的数字是栈中下面紧邻位置链表的最后一个位置

同样数字进栈的时候，将同样的数字对应的index串联在进栈位置链表的下一个位置

public static int[][] getNearLessNoRepeat(int[] arr) {
    int[][] res = new int[arr.length][2];
    // 只存位置！
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) { // 当遍历到i位置的数，arr[i]
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
            int j = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[j][0] = leftLessIndex;
            res[j][1] = i;
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int j = stack.pop();
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
        res[j][0] = leftLessIndex;
        res[j][1] = -1;
    }
    return res;
}

public static int[][] getNearLess(int[] arr) {
    int[][] res = new int[arr.length][2];
    Stack<List<Integer>> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
        while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
            List<Integer> popIs = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            for (Integer popi : popIs) {
                res[popi][0] = leftLessIndex;
                res[popi][1] = i;
            }
        }
        if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
            stack.peek().add(Integer.valueOf(i));
        } else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
        }
    }
    while (!stack.isEmpty()) {
        List<Integer> popIs = stack.pop();
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
        for (Integer popi : popIs) {
            res[popi][0] = leftLessIndex;
            res[popi][1] = -1;
        }
    }
    return res;
}

Leetcode 739.每日温度

单调栈解法
可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数设为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

Leetcode 42. 接雨水

此题也是找一个从下到上单调递减的栈

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s;
        int retVal = 0;
        for(int i = 0; i<height.size(); ++i)
        {
            if(!s.size())
            {
                s.push(i);
                continue;
            }
            int tmp = s.top();
            while(s.size() && height[i]>height[tmp])
            {
                s.pop();
                if(s.size() == 0)break;
                int w = i-s.top()-1;
                int h = min(height[i], height[s.top()]) - height[tmp];
                retVal+=w*h;
                tmp = s.top();
            }
            
            s.push(i);
        }
        return retVal;
    }
};

Leetcode 84. 柱状图中最大的矩形

随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 i 能够扩展到的最远范围。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        int maxArea = heights[0];
        for(int i = 0; i<heights.size(); ++i)
        {
            maxArea = max(maxArea, heights[i]);
            if(!s.size())
            {
                s.push(i);
                continue;
            }
            // 维护一个从下到上递增的栈
            while(s.size()>1 && heights[i]<heights[s.top()])
            {
                int tmp = s.top();
                s.pop();
                int l = s.top();
                maxArea = max(maxArea, heights[tmp]*(i-l-1));
            }
            s.push(i);
        }
        return maxArea;
    }
};

Leetcode 155.最小栈

当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

问题

无重复数字

有重复数字

Leetcode 739.每日温度

Leetcode 42. 接雨水

Leetcode 84. 柱状图中最大的矩形

Leetcode 155.最小栈