刷题日志--差分与单调栈 6.1

小明的彩灯

来源：https://www.lanqiao.cn/problems/1276/learning/

问题叙述

题目描述
小明拥有 N 个彩灯，第 i 个彩灯的初始亮度为 ai。

小明将进行 Q 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。

求 Q 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。

输入描述

第一行包含两个正整数 N，QN，Q，分别表示彩灯的数量和操作的次数。
第二行包含 NN 个整数，表示彩灯的初始亮度。
接下来 QQ 行每行包含一个操作，格式如下：
l r x，表示将区间 l∼r 的彩灯的亮度 +x。

1 ≤ N,
Q ≤ 5×10^5,
0 ≤ ai ≤ 10^9,
1 ≤ l ≤ r ≤ N,
-10^9 ≤ x ≤ 10^9

输出描述

输出共 1 行，包含 N 个整数，表示每个彩灯的亮度。

输入输出样例
示例 1
输入
5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100

输出
0 5 5 6 10

运行限制

最大运行时间：1s
最大运行内存: 128M

分析

前缀和与差分。

将l到r范围内的所有彩灯+x（包括l和r），那我们直接将l位置的彩灯+x，r+1位置的彩灯-x，然后求其前缀和，就能将l到r范围内的彩灯都+x，而范围之外的彩灯不受影响。

所以创建一个tmp数组，用来存储彩灯亮度变化，用res数组存放初始状态，最终的结果即为初始状态加上变化。

注意：直接用Scanner会超时，所以这里用了流加速读入数据

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static long[] res = new long[500005];
    static long[] tmp = new long[500005];

    public static void main(String[] args) throws IOException {
        //卡时间，流加速读入
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] o = bf.readLine().split(" ");
        int N = Integer.parseInt(o[0]);
        int Q = Integer.parseInt(o[1]);

        //存放一下初始状态
        String[] t = bf.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            res[i] = Long.parseLong(t[i]);
        }
        //l位置的彩灯亮度+x，r+1位置的彩灯亮度-x
        while (Q-- > 0) {
            String[] s = bf.readLine().split(" ");
            int l = Integer.parseInt(s[0]) - 1;
            int r = Integer.parseInt(s[1]) - 1;
            long x = Long.parseLong(s[2]);
            tmp[l] += x;
            tmp[r + 1] -= x;
        }
        //求出前缀和，l到r范围内的彩灯亮度就都+x了
        for (int i = 1; i < N; i++) {
            tmp[i] += tmp[i - 1];
        }
        for (int i = 0; i < N; i++) {
            //初始状态+变化=结果
            //负数的话，按0计算，所以干脆直接和0比较
            System.out.print(Math.max(0, res[i] + tmp[i]) + " ");
        }
    }
}

每日温度

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/daily-temperatures

问题叙述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：
1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

分析

初次做此类问题建议先手写一遍暴力，即针对每个温度值向后进行依次搜索，找到比当前温度更高的值。
写着写着就会发现规律，我们只需要维护一个递减栈就行，栈内存放的都是暂时没有找到更高温度的索引值
例如示例中的这个例子：temperatures = [73,74,75,71,69,72,76,73]
73入栈，74 > 73 ，73找到了更高温度，73出栈，用二者的索引值相减为1，即为73的结果。
74入栈，75 > 74 , 74找到了更高温度，74出栈，用二者的索引值相减为1，即为74的结果。
75入栈，71 < 75 , 没找到更高温度。
71入栈，69 < 71 , 没找到更高温度。
69入栈，72 > 69 , 69找到了更高温度，69出栈，用二者的索引值相减为1，即为69的结果。
72 > 71 , 71找到了更高温度，71出栈，用二者的索引值相减为2，即为71的结果。
72 < 75 , 72入栈。
76 > 72 , 72找到了更高温度，72出栈，用二者的索引值相减为1，即为72的结果。
76 > 75 , 75找到了更高温度，75出栈，用二者的索引值相减为1，即为75的结果。
73 < 76 , 73入栈。不满足条件，循环结束之后没有操作，默认值为0，故73和76的结果为0

建议手动模拟一下刚刚叙述的过程，加深理解。

由于这里是用栈存储的索引值，所以当我们出栈的时候，就能获取到这个索引值，用遍历的i，减去这个索引值index就是index这个索引值对应的结果
这么说可能有点绕，看下面的代码应该很容易理解

Code

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int index = stack.pop();
                ans[index] = i - index;
            }
            stack.push(i);
        }
        return ans;
    }
}

下一个更大元素II

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-ii

问题叙述

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。

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

示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]

解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

分析

单调栈

这道题跟上题几乎没有区别，就当练练手了，唯一的区别就是要循环的找下一个更大的数。

我们只要限定一下遍历次数为2 * n，然后遍历时对下标取模即可。

Code

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res,-1);
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < 2 * n; i++) {
            while (!stack.isEmpty() && nums[i % n] > stack.peek()) {
                int index = stack.pop();
                res[index] = nums[i % n];
            }
            stack.push(nums[i % n]);
        }
        return res;
    }
}