二、栈和队列

2.1 基本应用

2.1.1 逆波兰表达式求值

150. 逆波兰表达式求值

class Solution {/**思路分析：遇到数则压栈，遇到运算符则用最上层的两个数进行运算并将结果压栈*/public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();int n1,n2;for(String token : tokens){switch(token){case "+":// 加法n1 = stack.pop();n2 = stack.pop();stack.push(n1+n2);break;case "-":// 减法n1 = stack.pop();n2 = stack.pop();stack.push(n2-n1);break;case "*":// 乘法n1 = stack.pop();n2 = stack.pop();stack.push(n1*n2);break;case "/":// 除法n1 = stack.pop();n2 = stack.pop();stack.push(n2/n1);break;default: stack.push(Integer.parseInt(token)); // 为数字则压栈break;}}return stack.pop();}
}

2.1.2 有效的括号

20. 有效的括号

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();char[] chars = s.toCharArray();char cc;for(char c : chars){if(stack.isEmpty() || c=='(' || c=='{' || c=='['){stack.push(c);continue;}cc = stack.peek();if((cc == '(' && c == ')') || (cc == '{' && c == '}') || (cc == '[' && c == ']')){stack.pop();}else{stack.push(c);}}return stack.isEmpty();}
}

2.2 单调栈

单调栈：栈内元素保持单点递增或单调递减的栈
(以单调递增为例)
入栈规则:

• 新元素比栈顶元素小：直接入栈
• 新元素比栈顶元素大：弹出栈内元素直到栈顶比新元素小（或空栈）
  出栈意义：
• 需要出栈时，入栈的新元素是出栈元素有房第一个比出栈元素小的元素
• 出栈后，新的栈顶是出栈元素左侧最大的数
  技巧：最后添加一个值为0的哨兵结点，可以在最后强制所有元素出栈。
  以下分别使用了单调递增栈和单调递减栈

2.2.1 柱状图中最大的矩形

84. 柱状图中最大的矩形

class Solution {public int largestRectangleArea(int[] heights) {// 定义栈Stack<Integer> stack = new Stack<>();int max = 0;for(int i = 0;i <= heights.length;i++){int curHeight;if(i == heights.length){curHeight = 0; // 使用哨兵使栈中元素全部出栈}else{curHeight = heights[i];}while(!stack.isEmpty() && curHeight < heights[stack.peek()]){int ph = heights[stack.pop()];while(!stack.isEmpty() && heights[stack.peek()] == ph){stack.pop(); // 相同高度时，定位至最左侧的数}/**计算从右向左依次中间高度的右边界（即当前高度的下标）与左边界（栈中当前元素的前一个位置）之差。注意没有左边界的情况（即当前单调栈只有一个元素）*/int w = i - (stack.isEmpty() ? -1 : stack.peek()) - 1; max = Math.max(max,ph*w);}stack.push(i);}return max;}
}