962. 最大宽度坡

给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。

示例 1：
输入：[6,0,8,2,1,5] 输出：4 解释： 最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
示例 2：
输入：[9,8,1,0,1,9,4,0,4,1] 输出：7 解释： 最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.

提示：

  1. 2 <= A.length <= 50000
  2. 0 <= A[i] <= 50000

思路：
暴力：O(n2)
方法1：双关键字排序
方法2：维护递减序列(单调栈)+二分
方法3：单调栈+ 倒序遍历
方法4：树状数组
方法5：线性，维护前缀最小值和后缀最大值 + 双指针

思路：
方法1：双关键字排序
目的是找满足A[i] < A[j]的最小的i，故可考虑将下标连同该下标上的数一同排个序。
排序方法是第一关键字按照数字大小从小到大，第二关键字是按照下标从小到大。
这样遍历到当前下标时，位于该下标上的数字就是其在原数组中的下标，只需维护一个最小值就能更新最大坡宽。
时间复杂度：O(nlogn)

  1. class Solution {
  2.     public int maxWidthRamp(int[] nums) {
  3.         int n = nums.length;
  4.         Integer[] a = new Integer[n];
  5.         for (int i = 0; i < n; i++)
  6.             a[i] = i;
  7.         Arrays.sort(a, (o1, o2) -> (nums[o1] == nums[o2] ? o1 - o2 : nums[o1] - nums[o2]));
  8.         int res = 0, minIdx = a[0];
  9.         for (int x : a) {
  10.             res = Math.max(x - minIdx, res);
  11.             minIdx = Math.min(minIdx, x);
  12.         }
  13.         return res;
  14.     }
  15. }

方法2：单调栈 + 二分
维护一个严格单调递减序列，遍历到当前元素时，既能通过单调递减栈弹栈的方式找左侧第一个大于(等于)该元素的值/下标, 也能通过对单调递减序列二分的方式找最左侧小于(等于)该元素的值/下标。
时间复杂度：O(nlogn)

  1. class Solution {
  2.     public int maxWidthRamp(int[] nums) {
  3.         int n = nums.length;
  4.         int[] stk = new int[n];
  5.         int p = -1, res = 0;
  6.         for (int i = 0; i < n; i++) {
  7.             int x = nums[i];
  8.             int l = 0, r = p;
  9.             while (l < r) {
  10.                 int mid = l + r >> 1;
  11.                 if (nums[stk[mid]] > x)
  12.                     l = mid + 1;
  13.                 else
  14.                     r = mid;
  15.             }
  16.             if (nums[stk[l]] <= x)
  17.                 res = Math.max(res, i - stk[l]);
  18.             if (p == -1 || nums[i] < nums[stk[p]])
  19.                 stk[++p] = i;
  20.         }
  21.         return res;
  22.     }
  23. }

方法3：单调栈 + 倒序遍历
从前往后遍历生成一个严格单调递减序列，倒序考虑当前栈顶下标对应的值是否小于当前值，如果是，更新答案，弹栈并继续判断栈顶下标对应的值是否小于当前值，如果不是，继续处理下一个数。
时间复杂度：O(n)

  1. class Solution {
  2.     public int maxWidthRamp(int[] nums) {
  3.         int n = nums.length;
  4.         int[] stk = new int[n];
  5.         int p = -1, res = 0;
  6.         for (int i = 0; i < n; i++)
  7.             if (p < 0 || nums[i] < nums[stk[p]])
  8.                 stk[++p] = i;
  10.         for (int i = n - 1; i >= 0 && p > -1; i--) {
  11.             while (p > -1 && nums[i] >= nums[stk[p]]) {
  12.                 res = Math.max(i - stk[p--], res);
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. }

方法4：树状数组：又学到一种树状数组的用法
由于本题数组长度与数值范围一致，故可用树状数组解决。
从前往后遍历，依据当前元素更新：在树状数组中找到小于等于当前元素值出现的最小下标。

  1. class Solution {
  2.     int N = 50010;
  3.     public int maxWidthRamp(int[] nums) {
  4.         int res = 0;
  6.         BIT bit = new BIT(N);
  7.         for (int i = 0; i < nums.length; i++) {
  8.             int x = nums[i] + 1;
  9.             res = Math.max(res, i - bit.min(x));
  10.             bit.add(x, i);
  11.         }
  12.         return res;
  13.     }
  15.     class BIT {
  16.         int[] a;
  17.         int n;
  19.         BIT(int n) {
  20.             this.n = n;
  21.             a = new int[n + 1];
  22.             Arrays.fill(a, n + 1);
  23.         }
  25.         void add(int idx, int x) {
  26.             for (int i = idx; i <= n; i += i & (-i)) {
  27.                 a[i] = Math.min(a[i], x);
  28.             }
  29.         }
  31.         int min(int idx) {
  32.             int res = n + 1;
  33.             for (int i = idx; i > 0; i -= i & (-i)) {
  34.                 res = Math.min(a[i], res);
  35.             }
  36.             return res;
  37.         }
  38.     }
  39. }

1124. 表现良好的最长时间段

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。

示例 1：
输入：hours = [9,9,6,0,6,6,9] 输出：3 解释：最长的表现良好时间段是 [9,9,6]。
示例 2：
输入：hours = [6,6,6] 输出：0

提示：

  • 1 <= hours.length <= 104
  • 0 <= hours[i] <= 16

思路：
错误方法：前缀和 + 二分答案
本题不满足二分性
例 8 10 6 16 5，大于8表示满足要求用1表示，否则不满足用-1表示。其前缀和数组为-1 0 -1 0 -1
如果用二分，第一次mid = (0+4+1) / 2 = 2， 没有满足要求的(没有连续2天能使劳累天数大于非劳累天数)，故r = mid - 1 = 1
第二次mid = (0 + 1 + 1) / 2 = 1, 有满足要求的，故l = mid = 1
第三次退出循环。结果输出1，但是应该是3才对。
方法1：
前缀和 + 哈希 + 贪心
大于8表示满足要求用1表示，否则不满足用-1表示。

  1.   - 计算前缀和
  2.   - 加入 `0 = -1`到哈希表方便计算
  3.   - 遍历数组，找到哈希表中第一个小于当前元素的第一个元素的下标(**越长越好，先有-1，才会有-2，故只需在哈希表中查找比当前元素小一的元素即可**)
  4.   - 若哈希表中不存在当前元素，存入当前元素及其下标,否则不存入(**贪心**)。
  1. class Solution {
  2.     public int longestWPI(int[] hours) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  6.         int sum = 0, res = 0;
  7.         for (int i = 0; i < hours.length; i++) {
  8.             hours[i] = hours[i] > 8 ? 1 : -1;
  9.             sum += hours[i];
  11.             if (sum > 0)
  12.                 res = Math.max(res, i + 1);
  13.             else {
  14.                 if (map.containsKey(sum - 1))
  15.                     res = Math.max(res, i - map.get(sum - 1));
  16.                 if (!map.containsKey(sum))
  17.                     map.put(sum, i);
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. }
  1. 方法2：单调栈 + 贪心
  3.   - 计算前缀和
  4.   - 遍历前缀和数组，记录一个单调递减栈
  5.   - 从后往前贪心，能弹栈就弹栈
  1. class Solution {
  2.     public int longestWPI(int[] hours) {
  3.         Deque<Integer> stack = new LinkedList<>();
  4.         int n = hours.length;
  5.         int[] a = new int[n + 1];
  6.         for (int i = 0; i < hours.length; i++) {
  7.             hours[i] = hours[i] > 8 ? 1 : -1;
  8.             a[i + 1] = a[i] + hours[i];
  9.         }
  11.         for (int i = 0; i <= n; i++) {
  12.             if (stack.isEmpty() || a[stack.peek()] > a[i])
  13.                 stack.push(i);
  14.         }
  15.         int res = 0;
  16.         for (int i = n; i >= 0; i--) {
  17.             if (stack.isEmpty()) break;
  18.             while (!stack.isEmpty() && a[i] > a[stack.peek()]) {
  19.                 int l = stack.pop();
  20.                 res = Math.max(res, i - l);
  21.             }
  22.         }
  23.         return res;
  24.     }
  25. }

其它例题：
AcWing 4487. 最长连续子序列