LC155. Min Stack
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
class MinStack {
//思想就是建两个栈，一个是正常的操作，另一个是存放实时的最小值
private Stack<Integer> stack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int x) {
stack.push(x);
if(minStack.isEmpty()){
minStack.push(x);
} else {
minStack.push(Math.min(x, minStack.peek()));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
LC232. Implement Queue using Stacks
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
private void stack2ToStack1(Stack stack1, Stack stack2){
while(!stack2.isEmpty()){
stack1.push(stack2.pop());//第二个栈先判断第一个栈是不是非空，再把元素一一添加进第二个栈
}
}
/** Push element x to the back of queue. */
public void push(int x) {
stack2.push(x);//第一个栈正常放入数
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
this.stack2ToStack1(stack1, stack2);
return stack1.pop();
}
/** Get the front element. */
public int peek() {
this.stack2ToStack1(stack1, stack2);
return stack1.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
this.stack2ToStack1(stack1, stack2);
return stack1.isEmpty();
}
}
LC84. Largest Rectangle in Histogram
Input: [2,1,5,6,2,3]
Output: 10
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0;
Stack<Integer> stack = new Stack<Integer>();
int max = 0;
for (int i = 0; i <= heights.length; i++){
int cur = (i == heights.length) ? -1 : heights[i];//在最后的末位补上-1，能让单调栈中的所有元素都能pop出来。
while(!stack.isEmpty() && cur <= heights[stack.peek()]){//当有元素小于栈顶的元素时，需要把栈顶的元素pop掉，此时恰巧可以计算以pop掉的元素为最小高度的最大面积
int height = heights[stack.pop()];//此时已经pop掉了栈顶元素所以后续有可能是空的。
int width = stack.isEmpty() ? i : i-stack.peek()-1;//如果是空的说明pop掉的元素的右边没有元素了，宽度就是i
max = Math.max(max, height*width);
}
stack.push(i);
}
return max;
}
LC42. Trapping Rain Water
public int trap(int[] height) {
Stack<Integer> stack = new Stack<>();
int sum = 0;
int i = 0, j = height.length;
while(i < j){
if (stack.isEmpty() || height[i] <= height[stack.peek()]){//这句话是保证潜在bottom永远比栈顶元素小才有可能形成坑
stack.push(i++);
} else {//代表后面的元素比目前的栈顶元素大，这样bottom比两边都小所以形成了坑
int bottom = stack.pop();
if(stack.isEmpty()) continue; //如果bottom 后面没有栈元素了，那形成不了坑
sum += (Math.min(height[i], height[stack.peek()]) - height[bottom]) * (i - stack.peek() - 1);// 坑的左右两面的高度的最小值减去bottom然后乘以两面高度的的坐标的差减一。
}
}
return sum;
}
LC225. Implement Stack using Queues
class MyStack {
Queue<Integer> q1;
Queue<Integer> q2;
/** Initialize your data structure here. */
public MyStack() {
q1 = new LinkedList<Integer>();
q2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
if (!q1.isEmpty()){
q1.add(x);
} else {
q2.add(x);
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
int x = 0;
if (q2.isEmpty()){
while (!q1.isEmpty()){
x = q1.remove();
if(!q1.isEmpty()){
q2.add(x);
}
}
} else if (q1.isEmpty()){
while (!q2.isEmpty()){
x = q2.remove();
if (!q2.isEmpty()){
q1.add(x);
}
}
}
return x;
}
/** Get the top element. */
public int top() {
int x = 0;
if (q2.isEmpty()){
while (!q1.isEmpty()){
x = q1.remove();
q2.add(x);
}
} else if (q1.isEmpty()){
while (!q2.isEmpty()){
x = q2.remove();
q1.add(x);
}
}
return x;
}
/** Returns whether the stack is empty. */
public boolean empty() {
if (q1.isEmpty() && q2.isEmpty()) return true;
else return false;
}
}
LC71. Simplify Path
···
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
String[] str = path.split("/");// 把字符串分割成只含有"","..","."和文件路径的字符串数组
for(String s : str){
if(s.equals("..")){
if(!stack.isEmpty())
stack.pop(); //如果他的前置文件路径是遇到..，他的前置文件路径就要被pop掉
} else if (!s.equals(".") && !s.equals("")){
stack.push(s);//遇到没有"","."的说明是正常路径
}
}
String res = "";
while(!stack.isEmpty()){
res = "/" + stack.pop() + res;
}
if (res.length() == 0) return "/";
return res;
}
···
LC150. Evaluate Reverse Polish Notation
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens){
if (token.equals("+")){
stack.push(stack.pop() + stack.pop());
} else if (token.equals("-")){
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
} else if (token.equals("*")){
stack.push(stack.pop() * stack.pop());
} else if (token.equals("/")){
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
LC20. Valid Parentheses
Input: "{[]}"
Output: true;
public boolean isValid(String s) {
char[] strs =s.toCharArray();
Stack<Character> stack = new Stack<>();
for (Character str : strs){
if(str == '('){
stack.push(')');
} else if (str == '['){
stack.push(']');
} else if (str == '{'){
stack.push('}');//遇到一个左括号，就把右括号放进栈里，根据栈的特性，当遇到不是左括号时，栈顶的元素一定时最后一个左括号对应的右括号
} else {
if (stack.isEmpty() || stack.pop() != str){
return false;//如果未遍历完栈空了，或者pop出的不是元素则是false
}
}
}
return stack.isEmpty(); //最后根据对称性，栈应该是空的
}
- Basic Calculator II
// String/stack
//3+5-4/6, 先在第一个数前加+，因为不可能是负数，所以sign是+
//步骤是 3 +? -> +3,0, 5 +? -> +5, 0
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num = 0;
for (int i = 0; i < s.length(); i++){
char c =s.charAt(i);
if (Character.isDigit(c)){
num = num*10 + c -'0';
}// 累加数字
if (c!=' ' && !Character.isDigit(c) || i + 1 == s.length()){
if (sign == '+'){
stack.push(num);
} else if (sign == '-'){
stack.push(-num);
} else if (sign == '/'){
stack.push(stack.pop() / num);
} else if (sign == '*'){
stack.push(stack.pop() * num);
}
sign = c;
num = 0;
}
}
int res = 0;
while(!stack.isEmpty()){
res += stack.pop();
}
return res;
}
LC224. Basic Caculator
class Solution {
// 3 + (5 + 4)
public int calculate(String s) {
int res = 0, num = 0, sign = 1;
Stack<Integer> stack = new Stack<>();
char[] chars = s.toCharArray();
for (Character c : chars){
if(Character.isDigit(c))
num = num*10 + c - '0';
if(c == '+' || c == '-'){
res += sign * num;//计算的是前一次的数
sign = (c == '+') ? 1 : -1;
num = 0;
} else if (c == '('){
stack.push(res);
stack.push(sign); // 记录括号前的总和和符号
res = 0;
sign = 1; //初始化和和符号
} else if (c == ')'){
res += sign * num;
num = 0;
res *= stack.pop();
res += stack.pop();//计算完括号里的9，再把括号外的和加上，第一个stack.pop是括号外的符号
}
}
res += sign*num;
return res;
}
}
