Tag: 前缀和

Posted 2022-08-27Updated 2022-08-27LeetCode / Hard / 复习2 minutes read (About 231 words)

363. Max Sum of Rectangle No Larger Than K

Question

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Solution

前缀和，计算矩阵中每个位置对应的方形的和。
遍历方形的两个对角线上的点。
其面积等于大块加小块的面积减去两个长方形的面积。
如果面积有小于k的，则记录其最大值并返回。

Code

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int x = matrix.length, y = matrix[0].length, max = Integer.MIN_VALUE;
        int[][] sum = new int[x+1][y+1];
        
        for(int i = 1; i <= x; i++){
            int total = 0;
            for(int j = 1; j <= y; j++){
                total += matrix[i-1][j-1];
                sum[i][j] = sum[i-1][j] + total;
            }
        }
 
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                for(int m = i + 1; m <= x; m++){
                    for(int n = j + 1; n <= y; n++){
                        int area = sum[m][n] + sum[i][j] - sum[m][j] - sum[i][n];
                        if(area <= k) max = Math.max(max, area);
                    }
                }
            }
        }
        return max;
    }
}

Posted 2022-06-12Updated 2022-06-11LeetCode / Hard3 minutes read (About 380 words)

2302. Count Subarrays With Score Less Than K

Question

The score of an array is defined as the product of its sum and its length.

For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Solution

第一次在contest中做出hard题目，而且还是超过100%，庆祝一下！（不过因为前一道题做的太久没提交上去……

滑动窗口

数组内全部为正整数，当选择的子数组的尺寸增加时，其乘积是单调递增的。因此可以采用滑动窗口，在循环时维护窗口内数字的和sum和当前的乘积product。

每次将一个新的右侧元素滑入窗口，更新窗口内的sum值，并计算product值。当当前product大于k时，则将左侧的元素滑出窗口，并更新sum和product值。

调整完窗口尺寸后，由于新的right位置可以和前面的每一个子数组组成一个新的数组，因此将count加上当前的left到right的个数即可。

循环结束后返回count。

Code

class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0, sum = 0;
        int left = 0, right = 0;
        
        while(right < nums.length){
            sum += nums[right]; //右侧滑入窗口
            long product = sum * (right - left + 1);
            
            while(product >= k){    //当乘积大于k时，左侧滑出窗口
                sum -= nums[left];
                left++;
                product = sum * (right - left + 1);
            }
            count += right - left + 1;  //计算新的right位置可组成的新组合
            right++;
        }
        return count;
    }
}

Posted 2022-06-03Updated 2022-06-03LeetCode / Medium3 minutes read (About 432 words)

304. Range Sum Query 2D - Immutable

Question

Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.

int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Solution

前缀和/动态规划，用一个dp[][]数组记录到matrix[0][0]到matrix[i][j]区域的和。

计算两个点之间形成的总数只需用外侧的位置的前缀和加上内侧位置的前缀和，然后减去两者交换长宽位置的前缀和即可。

递推公式

计算dp[][]数组时，需要将其上侧与左侧所有数字加和，并加上matrix[][]上该位置对应的元素。
用dp[i][j-1] - dp[i-1][j-1]计算出左侧所有数字之和，dp[i-1][j]则是上侧所有数字之和。

Code

class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j] + matrix[i-1][j-1];
            }
        };
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row1][col1] + dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Solution 2

暴力搜索，直接计算从row1, col1到row2, col2的元素加和。

Code

class NumMatrix {
    int[][] mat;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i <= row2; i++){
            for(int j = col1; j <= col2; j++){
                sum += mat[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Posted 2022-05-22Updated 2022-05-22LeetCode / Hard / 复习6 minutes read (About 974 words)

2281. Sum of Total Strength of Wizards

Question

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the ith wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:

The strength of the weakest wizard in the group.

The total of all the individual strengths of the wizards in the group.

Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Solution

参考连接

根据题意，我们需要的结果是所有子数列乘以该子数列中最小值之和。

数组strength[]中的每一个元素，都充当一定范围内的子数列的最小值。因此我们需要**确定每个元素充当最小值的范围(left, right)**。然后计算这个元素可以组成的子数列的和与这个元素的乘积。

我们的问题相当于确定下一个更小元素，而单调栈专门处理这一类问题——“下一个更大/更小元素”
496. Next Greater Element I

通过单调栈，我们可以确定最小值为strength[i]的子数列的范围(left, right)，并将其保存在两个数组left[]与right[]中。

最后通过前缀和的计算，来确定(left, right)范围内的子数列之和。

单调栈

新建两个数组left[]， right[]保存以strength[i]为最小值的范围。

维护两个单调栈，保证下列关系：
strength[left] < strength[i]
strength[right] <= strength[i]

其中，left取小于号，而right可以等于是为了取值不重复。

注意，单调栈保存的是下标，这样使用起来更加灵活。

前缀和

为了得到范围（left, right）内的所有子数列之和。我们可以观察left, i, right之间的关系。

…left-1, left, left + 1, left + 2, … i-1, i, i+1, … right-1, right, right+1…

开始于 left+1的子数列:
sum(left+1, … i) = prefix[i + 1] - prefix[left + 1]
sum(left+1, … i+1) = prefix[i + 2] - prefix[left + 1]
…
sum(left+1, … right-1) = prefix[right] - prefix[left + 1]
开始于left+2的子数列:
sum(left+2, … i) = prefix[i + 1] - prefix[left + 2]
sum(left+2, … i+1) = prefix[i + 2] - prefix[left + 2]
…
sum(left+2, … right-1) = prefix[right] - prefix[left + 2]
…
开始于i的子数列:
sum(i, … i) = prefix[i + 1] - prefix[i]
sum(i, … i+1) = prefix[i + 2] - prefix[i]
…
sum(i, … right-1) = prefix[right] - prefix[i]

合并这些式子，我们可以得到：

正数部分:
(prefix[i + 1] + prefix[i + 2] + ... + prefix[right]) * (i - left)
负数部分:
(prefix[left + 1] + prefix[left + 2] + ... + prefix[i]) * (right - i)

最后我们可以提前计算前缀和的前缀和来优化计算步骤，注意计算时需要将各个部分模除以保证不超过范围。
正数部分模除后需要加上MOD以保证其减去负数部分的结果大于0。

Code

class Solution {
    public int totalStrength(int[] strength) {
        long MOD = 1_000_000_007;
        int n = strength.length;
        
        Deque<Integer> mono = new ArrayDeque<>();
        int[] left = new int[n], right = new int[n];
        
        for(int i = 0; i < strength.length; i++){   //单调栈，记录比当前元素strength[i]小的第一个左侧位置strength[left]
            while(!mono.isEmpty() && strength[mono.peek()] >= strength[i]){
                mono.pop();
            }
            left[i] = mono.isEmpty() ? -1 : mono.peek();
            mono.push(i);
        }
        mono.clear();
        for(int i = n-1; i >=0; i--){   //单调栈，记录比当前元素strength[i]小的第一个右侧位置strength[right]
            while(!mono.isEmpty() && strength[mono.peek()] > strength[i]){
                mono.pop();
            }
            right[i] = mono.isEmpty() ? n : mono.peek();
            mono.push(i);
        }
        
        long[] prefix = new long[n+1], prefix_sum = new long[n+2];
        
        for(int i = 1; i <= strength.length; i++){  //计算前缀和
            prefix[i] = (prefix[i-1] + strength[i-1]) % MOD;
        }
        
        for(int i = 2; i <= strength.length+1; i++){    //计算前缀和的前缀和
            prefix_sum[i] = (prefix_sum[i-1] + prefix[i-1]) % MOD;
        }
        
        long res = 0;
        
        for(int i = 0; i < n; i++){
            res += ((prefix_sum[right[i] + 1] - prefix_sum[i + 1]) * (i - left[i]) % MOD + MOD -    //这里加MOD是为了保证前项大于后项，防止出现负数
                    (prefix_sum[i + 1] - prefix_sum[left[i] + 1]) * (right[i] - i) % MOD ) * strength[i];
            res %= MOD;
        }
        
        return (int) res;
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}

Question

Solution

Code

Question

Solution

滑动窗口

Code

Question

Solution

递推公式

Code

Solution 2

Code

Question

Solution

单调栈

前缀和

Code

Question

Solution

Code

Recents

Archives

Links