前缀后缀法

剑指 Offer 66. 构建乘积数组

238. 除自身以外数组的乘积

768. 最多能完成排序的块 II

6190. 找到所有好下标

该类型的题目最大的特点：

• 判断一个数左右两边是否满足要求
• 求一个数左右两边的乘积

整体思路：用两个数组，分别统计「从左到右」和「从右到左」的信息

直接看题吧！！

构建乘积数组

题目详情可见 剑指 Offer 66. 构建乘积数组

对于这个题目，用两个数组分别统计「从左到右」和「从右到左」的乘积

「从左到右」：left[i]表示[0...i-1]的乘积

「从右到左」：right[i]表示[i+1...n-1]的乘积

xxxxxxxxxx
public int[] constructArr(int[] a) {
    int n = a.length;
    int[] left = new int[n];
    int[] right = new int[n];
    int product = 1;
    for (int i = 0; i < n; i++) {
        left[i] = product;
        product *= a[i];
    }
    product = 1;
    for (int i = n - 1; i >= 0; i--) {
        right[i] = product;
        product *= a[i];
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        ans[i] = left[i] * right[i];
    }
    return ans;
}

除自身以外数组的乘积

题目详情可见 除自身以外数组的乘积

几乎和上一题一模一样！！

最多能完成排序的块 II

题目详情可见 最多能完成排序的块 II

用两个数组分别存前缀最大值和后缀最小值

如果i和i + 1之间可以分块，那么必有prefMax[i] <= suffMin[i + 1]

xxxxxxxxxx
public int maxChunksToSorted(int[] arr) {
    int n = arr.length;
    int[] prefMax = new int[n];
    int[] suffMin = new int[n];
    prefMax[0] = arr[0];
    for (int i = 1; i < n; i++) prefMax[i] = Math.max(prefMax[i - 1], arr[i]);
    suffMin[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; i--) suffMin[i] = Math.min(suffMin[i + 1], arr[i]);
    int ans = 1;
    for (int i = 0; i < n - 1; i++) {
        if (prefMax[i] <= suffMin[i + 1]) ans++;
    }
    return ans;
}

找到所有好下标

题目详情可见 找到所有好下标

对于这个题目，用两个数组分别统计「从左到右」和「从右到左」的最长非递增/非递减的子数组长度

「从左到右」：left[i]表示[0...i-1]中最长非递增的长度

「从右到左」：right[i]表示[i+1...n-1]的最长非递减的长度

public List<Integer> goodIndices(int[] nums, int k) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        left[i] = cnt;
        if (i > 0 && nums[i - 1] < nums[i]) cnt = 0;
        cnt++;
    }
    cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        right[i] = cnt;
        if (i < n - 1 && nums[i] > nums[i + 1]) cnt = 0;
        cnt++;
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (left[i] >= k && right[i] >= k) ans.add(i);
    }
    return ans;
}