Skip to main content

Stack 堆栈

定义​

  • 特性: LIFO (Last in First Out)
  • 适用于需要记录之前的状态，必要的时候可以回到之前的状态，或者利用之前的值
  • 不像 array，不能用 index 访问，只能每次拿栈顶元素
题外话: 动态规划 Dynamic Programming
  • DP: 记录之前所有状态，随时可能访问任何一个字问题，所以通常用 Array 或者 HashTable，而且不会回到之前的状态，只会利用之前的值
  • Stack: 每次只需要栈顶元素，并且每个状态只会被用 O(1)次

常用方法​

  • peek(): 获取但是不移除队列头部元素，队列为空返回 null。
  • push(): 将一个元素推入双端队列表示的堆栈，即队列的头部。成功返回 true，如果没有可用空间，抛出 IllegalStateException。
  • pop(): 从双端队列表示的堆栈 中弹出一个元素。
  • size(): 返回双端队列元素数。
  • isEmpty(): 判断队列是否为空，为空返回 true。

解题思路​

定义好 Stack 的含义

  • 在 arr[i]左侧所有比 arr[i] 大的数
  • 递归之前的函数状态(Call Stack)
tip

一般从后往前看，而且这个回头一般只回头一次，因为数据会被取出。

需要回头看的话，一般选 stack 或者 DP 的解题方法。

Q739 例题​

Given an array of integers temperatures represents the daily temperatures, return an 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]

分析​

  • Find the distance to next greater element for each arr[i]
  • Stack Definition: All the elements (index) to the right of arr[i] that are greater than arr[i]
  • Top of Stack: Next greater element to the right of arr[i]

High Level Idea​

  1. Initialize stack
  2. For each element arr[i] backwards
    • a. Pop until stack is empty or top of stack > arr[i]
  3. Calculate distance from arr[i] to top of stack
  4. Repeat

代码​

public int dailyTemperatures(int[] T) {
    int n = T.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int = n-1; i >= 0; i--) {
        while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
            stack.pop();
        }

        if (stack.isEmpty()) {
            res[i] = 0;
        } else {
            res[i] = stack.peek() - i;
        }

        stack.push(i);
    }

    return res;
}

Q735 例题​

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.

分析​

  • Stack Definition: All asteriods left so far
  • Top of Stack: Closest survived asteriod to the left of arr[i]

High Level Idea​

  1. Initialize Stack
  2. For each arr[i]
    • if arr[i] > 0, push to stack
    • else keep popping "smaller" util stack is empty or top element < 0
    • spcial dealing with "equal"
    • push arr[i] to stack if survived
  3. Repeat

代码​

public int[] asteriodCollision(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;
}

更多例题​

  • Valid Parentheses (20) -> Done
  • Next Greater Element I (496) -> Done
  • Next Greater Element II (503) -> Done
  • Decode String (394) -> Done
    • Two stacks to note last state
    • Reccursion of dfs
  • Exclusive Time of Functions (636)
  • Largest Rectangle in Histogram (84)

来源​