算法题解之单调栈和单调队列

Algorithm , 评论

单调栈

栈是很简单的⼀种数据结构， 先进后出的逻辑顺序， 符合某些问题的特点， ⽐如说函数调⽤栈。

单调栈实际上就是栈， 只是利⽤了⼀些巧妙的逻辑， 使得每次新元素⼊栈后， 栈内的元素都保持有序（单调递增或单调递减） 。

leetcode有一些题目可以使用单调栈来解决。

leetcode496. 下一个更大元素 I

给定两个没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].

输出: [-1,3,-1]

解释:

对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。

对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。

对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].

输出: [3,-1]

解释:

对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。

对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] ans = new int[nums2.length];
        int[] res = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = nums2.length-1; i >= 0; i--){
            while(!stack.isEmpty() && nums2[i] >= stack.peek()){
                stack.pop();
            } 
            int tmp =  stack.isEmpty()? -1 : stack.peek();
            map.put(nums2[i], tmp ); 
            stack.push(nums2[i]);
        }

        for(int i = 0; i < nums1.length; i++){
            res[i] = map.get(nums1[i]);
        }

        return res;
    }
}

leetcode739. 每日温度

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

这个问题本质上也是找 Next Greater Number， 只不过现在不是问你 Next Greater Number 是多少， ⽽是问你当前距离 Next Greater Number 的距离⽽已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] dailyTemperatures(int[] T) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[T.length];
        for(int i = T.length-1; i >= 0; i--){
            while( !stack.isEmpty() && T[stack.peek()] <= T[i]){
                stack.pop();
            }
            res[i] = stack.isEmpty()? 0 : stack.peek()-i;
            stack.push(i);
        }
        return res;

    }
}

如何处理「循环数组」

同样是 Next Greater Number， 现在假设给你的数组是个环形的， 如何处理？

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]

输出: [2,-1,2]

解释: 第一个 1 的下一个更大的数是 2；

数字 2 找不到下一个更大的数；

第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i = 2 * nums.length - 1; i >= 0 ; i--){
            while( !stack.isEmpty() && stack.peek()  <= nums[i % nums.length]){
                stack.pop();
            }
            res[i % nums.length] = stack.isEmpty() ? -1: stack.peek() ;
            stack.push(nums[i % nums.length]);
        }

        return res;

    }
}

或者开辟一个新数组，将原数组复制两份。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] nextGreaterElements(int[] nums) {
       int[] arr = new int[2*nums.length];
       for(int i = 0; i < arr.length; i++){
           arr[i] = nums[i % nums.length];
       }
       int[] res = new int[nums.length];
       Deque<Integer> stack = new ArrayDeque<>();
       for(int i = arr.length-1; i >= 0; i--){
           while(!stack.isEmpty() && arr[i] >= stack.peek()){
               stack.pop();
           }
           res[i % nums.length  ] = stack.isEmpty()?-1: stack.peek();

           stack.push(arr[i]);
       }

       return res;
    }
}

腾讯笔面试题：逛街

2021校招亲身经历的面试题，可惜了，当时没做出来

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述:
1
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。1<=n<=100000;1<=wi<=100000;
输出描述:
1
输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。
输入例子1:
1
2
6
5 3 8 3 2 5
输出例子1:
1
3 3 5 4 4 4
例子说明1:
1
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Scanner;
import java.util.Stack;
public class Main{

    public static int[] MaxBuilding(int[] arr){
        if(arr == null || arr.length < 0) return null;
        int[] res = new int[arr.length];
        Stack<Integer> stack = new Stack<>();
        // 从前向后遍历，维持一个递减栈
        for(int i = 0;i < arr.length;i++){
            res[i] = stack.size(); //前面能看到的数量
            while(!stack.isEmpty() && arr[i] >= arr[stack.peek()]){
                stack.pop();
            }
            stack.push(i);
        }
        stack.clear();
        // 从后向前遍历，同样维持递减栈
        for(int i = arr.length - 1;i >=0;i--) {
            res[i] = res[i] + 1 + stack.size();;//后面能看到的数量 + 自己
            while (!stack.isEmpty() && arr[i] >= arr[stack.peek()]) {
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] arr = new int[len];
        for(int i = 0 ; i < len ; i++){
            arr[i] = sc.nextInt();
        }
        int[] res = MaxBuilding(arr);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
    }

}

单调队列

所谓单调队列，就是在保持原始队列的先进先出的特性外，添加一个新方法getMax(), 可以以O(1)的时间复杂度获取当前队列的最大值。

字节亲身经历的面试题！！！可惜了

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MaxQueue {
    Deque<Integer> data = null;
    Deque<Integer> maxQ = null;

    public MaxQueue() {
        data = new ArrayDeque<>();
        maxQ = new ArrayDeque<>();
    }

    public int max_value() {
        if(!maxQ.isEmpty()){
            return maxQ.peek();
        }
        return -1;
    }

    public void push_back(int value) {
        while(!maxQ.isEmpty() && maxQ.peekLast() < value){
            maxQ.pollLast(); // 从后面出队列
        }
        maxQ.offerLast(value);
        data.offer(value);
    }

    public int pop_front() {

        if(data.isEmpty()){
            return -1;
        }
        int poll = data.peek();
        if(poll == maxQ.peek()){
            maxQ.poll();
        }
        data.poll();
        return poll;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

leetcode239. 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    class MonotonicQueue{
        private Deque<Integer> q;
        public MonotonicQueue(){
            q = new ArrayDeque<>();
        }
        private int max(){
            return q.peek();
        }

        private void push(int value){
            while(!q.isEmpty() && value > q.getLast()){
                q.pollLast();
            }
            q.offer(value);
        }

        private void pop(int value){
            if(!q.isEmpty() && q.peek() == value){
                q.pollFirst();
            }
        }

    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k == 0)    return new int[]{};
        MonotonicQueue q =  new MonotonicQueue();
        int[] res  = new int[nums.length - k + 1];
        int j = 0;
        for(int i = 0; i < nums.length; i++){
            if( i  < k -1){
                q.push(nums[i]);
            }else{
                // 窗口滑动
                q.push(nums[i]);
                res[j++] = q.max();
                q.pop(nums[i- k + 1]); //  移除窗口的最后一个元素
            }

        }
        return res;

    }
}

朱宏梁Research & Develop

后端开发工程师