Stack

  • 特性：LIFO （Last In First Out）
  • 适用于需要记载之前的状况，必要的时分可以回到之前的状况，或者使用之前的值
  • 不像array，不能用index拜访，只能每次拿栈顶元素

题外话：动态规划 Dynamic Programming

DP: 记载之前所有状况，随时可以拜访任何一个子问题，所以通常用Array或者HashTable，而且不会回到之前的状况，只会使用之前的值

Stack：每次只需要栈顶元素，并且每个状况只会被用O(1)次

Stack Principle

界说好Stack的意义

  • 在arr[i]左边所有比arr[i]大的数
  • 递归之前的函数状况（Call Stack）

例题

739. Daily Temperature

Given an array of integers temperatures represents the daily temperatures, returnan array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

Solution:

Find the distance to the next greater element for each arr[i]

Stack Definition: All elements(index) to the right of arr[i] that are greater than arr[i] (monotone increasing stack)

Top of Stack: Next Greater element to the right of arr[i]

High Level Idea:

  1. Initialize the stack

  2. For each element arr[i] backwards (pop until stack is empty or top of stack > arr[i])

  3. Calculate the distance from arr[i] to top of the stack

  4. Repeat

    class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] res = new int[n]; Deque stack = new ArrayDeque<>(n); for(int i = n – 1; i >=0; i–) { while(!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) { stack.pop(); } if(stack.isEmpty()) { res[i] = 0; } else { res[i] = stack.peek() – i; } stack.push(i); } return res; }}

735. Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

  • 2 <= asteroids.length <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

Solution:

Stack Definition: All asteroid left so far

Top of Stack: Closest survived asteroid to the left of arr[i]

High Level Idea:

  1. Initialize Stack
  2. For each arr[i]:

a. if arr[i] > 0, push to stack

b. else keep popping “smaller” until stack is empty or top element < 0

c. special dealing with “equal”

d. push arr[i] to stack if survived

class Solution {    public int[] asteroidCollision(int[] asteroids) {        Deque<Integer> stack = new ArrayDeque<>();        for(int ast : asteroids) {            if(ast > 0) {                stack.push(ast);            } else {                while(!stack.isEmpty() && stack.peek() > 0 && stack.peek() < - ast) {                    stack.pop();                }                if(!stack.isEmpty() && stack.peek() == -ast) {                    stack.pop();                } else if(stack.isEmpty() || stack.peek() < 0) {                    stack.push(ast);                }            }        }        int[] res = new int[stack.size()];        for(int i = res.length - 1; i >=0; i--) {            res[i] = stack.pop();        }        return res;    }}