左右两数组法

剑指 Offer 66. 构建乘积数组

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

6190. 找到所有好下标

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

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

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

直接看题吧！！

构建乘积数组

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

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

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

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

x
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;
}

除自身以外数组的乘积

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

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

找到所有好下标

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

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

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

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

xxxxxxxxxx
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;
}