# 栈：从普通栈到单调栈

请添加图片描述

# 栈的应用场景

栈是一种先进后出的数据结构（类比弹夹），在程序执行过程中，栈可以说是应用最广泛的数据结构之一了。

Java方法执行的时候会把方法的相关信息封装到一个栈帧放入虚拟机中。例如当methodOne调用methodTwo，methodTwo调用methodThree执行时，虚拟栈如下所示。当methodThree执行完毕则会出栈，methodTwo执行完毕出栈。即方法调用入栈，方法执行出栈 请添加图片描述简单的一个表达式计算的过程也会用到操作数栈

（100+200）*300的计算过程如下

将100入栈
将200入栈
弹出栈顶的2个元素100和200，相加后入栈
将300入栈
弹出栈顶的2个元素300和200，相乘后入栈

# 有效括号

题目地址：LeetCode 20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

输入：s = "()[]{}"
输出：true

输入：s = "(]"
输出：false

一直往栈中放即可，出栈的情况只有如下三种

要放入的字符串为)且栈顶为(
要放入的字符串为]且栈顶为[
要放入的字符串为}且栈顶为{

当所有字符都放完的时候，如果栈为空说明括号有效，否则括号无效

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        Character temp = s.charAt(i);
        if (stack.isEmpty()) {
            stack.add(temp);
        } else if (temp == ')' && stack.peek() == '(') {
            stack.pop();
        } else if (temp == ']' && stack.peek() == '[') {
            stack.pop();
        } else if (temp == '}' && stack.peek() == '{') {
            stack.pop();
        } else {
            stack.add(temp);
        }
    }
    return stack.isEmpty();
}

# 单调栈

单调栈也是一种栈，只是在栈的基础上增加了一些新特性。每次新元素入栈后，从栈顶到栈底元素是递增或者递减的（严格递增还是非严格递增，我们需要根据题意来确定栈中是否可以存放相同的元素）

请添加图片描述以单调递增栈为例，进栈的流程如下。

假设当前进栈的元素为e，从栈顶开始遍历元素，把小于等于e的元素出栈，直到遇到一个大于e的元素或者栈为空为止，然后再把e压入栈中

将如下一组元素入栈的流程如下，单调递增栈的过程如下

4 1 3 7 5 6

操作	栈中的元素（栈底->栈顶）
4进栈	4
1进栈	4 1
1出栈，3进栈	4 3
3出栈，4出栈，7进栈	7
5进栈	7 5
5出栈，6进栈	7 6

单调栈主要用来解决如下几种问题

比当前元素更大的下一个或者前一个元素（单调递增栈）
比当前元素更小的下一个或者前一个元素（单调递减栈）

# 每日温度

题目地址：LeetCode 739. 每日温度

请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

比较裸的单调栈的问法，按照日期从后往前维护一个单调递增栈（严格递增）即可，因为要输出几天后，所以在栈中放数组的下标，这样既能获取到数组中的值，也能根据下标获取到间隔天数

public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = temperatures.length - 1; i >= 0; i--) {
        // 之后的天气都没今天高，出栈就行了
        while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
            stack.pop();
        }
        // 通过下标计算天数
        result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        stack.push(i);
    }
    return result;
}

# 看到的牛

题目地址：poj 3250 Bad Hair Day

一群高度不完全相同的牛从左到右站成一排，每头牛只能看见它右边的比它矮的牛的发型，若遇到一头高度大于或等于它的牛，则无法继续看到这头牛和后面的其他牛的发型。给出这些牛的高度，要求每头牛可以看到的牛的数量的和请添加图片描述输入

输入：3 1 2 1 4 1
输出：5

第1头牛能看到3头
第2头牛能看到0头
第3头牛能看到1头
第4头牛能看到0头
第5头牛能看到1头
第6头牛能看到0头

请添加图片描述 我们可以换个思路，依次求每个牛能被多少个牛看到，加和即为题目要求的每头牛可以看到的牛的数量的和

这个反向思考比较难，但是一旦有了这个思路，实现就比较简单了。维护一个单调递增栈（严格递增），每次放牛的时候，先把小于等于当前值的牛弹出，然后看栈中有多少牛（个数即为这个牛能被看到的次数，因为是单调递增栈哈）。每次放牛的时候就能知道这个牛能被多少个牛看到。

public int getSeeLowSum(int[] heights) {
    int sum = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < heights.length ; i++) {
        // 栈里面的牛比 i 这个牛还小，肯定看不到 i 这个牛以及之后的牛
        while (!stack.isEmpty() && stack.peek() <= heights[i]) {
            stack.pop();
        }
        // i 这个牛能被看到的次数
        sum += stack.size();
        stack.push(heights[i]);
    }
    return sum;
}

← 堆：求解 TopK 队列：从普通队列到单调队列 →