题目

类型：stack

解题思路

假设有 m 个区间，最终的表达式为 m 个等式 之和。

若某个 nums[i]，如果在这个区间中充当最大值，则在最终等式中以 的形式出现次，如果在 个区间中充当最小值，则在最终等式中以形式出现 次。

因此可以统计每个 nums[i] 成为区间最大值的次数和成为区间最小值的次数 ，为 nums[i] 对于最终答案的贡献。

考虑如何统计每个 nums[i] 成为区间最值的次数：

• nums[i] 作为区间最大值的次数：找到 nums[i] 左右最近一个不满足「小于等于 nums[i] 」的位置，记其为 p 和 q。此时区间左端点共有 i - p 个选择，区间右端点共有 q - i个选择，根据乘法原理，区间个数为 (i - p) * (q - i) 个；
• nums[i] 作为区间最小值的次数：同理，找到 nums[i] 左右最近一个不满足「大于等于 nums[i] 」的位置，记其为 p 和 q，区间个数为 (i - p) * (q - i) 个。

即问题切换为：使用「单调栈」找到某个 nums[i] 的左边/右边的最近一个符合某种性质的位置，从而知道 nums[i] 作为区间最值时，左右端点的可选择个数，再结合乘法原理知道 nums[i] 能够作为区间最值的区间个数，从而知道 nums[i] 对答案的贡献。

值得注意的是，由于 nums[i] 存在相同元素，因此上述两边均取等号的做法会导致某些区间被重复计算，因此我们可以令最近右端点的部分不取等号，确保区间统计不重不漏。

代码

class Solution {
    int n;
    public long subArrayRanges(int[] nums) {
        n = nums.length;
        // min[i] 为 nums[i] 作为区间最小值的次数；max[i] 为 nums[i] 作为区间最大值的次数
        long[] min = getCnt(nums, true), max = getCnt(nums, false);
        long ans = 0;
        for (int i = 0; i < n; i++) ans += (max[i] - min[i]) * nums[i];
        return ans;
    }
    long[] getCnt(int[] nums, boolean isMin) {
        int[] a = new int[n], b = new int[n];
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && (isMin ? nums[d.peekLast()] >= nums[i] : nums[d.peekLast()] <= nums[i])) d.pollLast();
            a[i] = d.isEmpty() ? -1 : d.peekLast();
            d.addLast(i);
        }
        d.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!d.isEmpty() && (isMin ? nums[d.peekLast()] > nums[i] : nums[d.peekLast()] < nums[i])) d.pollLast();
            b[i] = d.isEmpty() ? n : d.peekLast();
            d.addLast(i);
        }
        long[] ans = new long[n];
        for (int i = 0; i < n; i++) ans[i] = (i - a[i]) * 1L * (b[i] - i);
        return ans;
    }
}