区间计数相关题目 907,828

标签：arr 907 int 计数 length 828 new stack2 stack1

907. Sum of Subarray Minimums Medium

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

Constraints:

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

分析：

如果brute force的话，时间复杂度在O(N³)  或者 做优化后O(N²)

  [3] [3,1] [3,1,2] [3,1,2,4]

  [1] [1,2] [1,2,4]

  [2] [2,4]

  [4]

 

如果我们从每个数字角度考虑的话，会发现：

3可以贡献的只有一次[3]

1可以贡献的有 [3,1] [3,1,2] [3,1,2,4] [1] [1,2] [1,2,4]

2可以贡献的有  [2] [2,4]

4可以贡献的只有 [4]

 

因此，针对1 ，可以贡献的次数为：

[3,1,2,4]   left=-1(左侧小于1的位置), right=4（右侧小于1的位置）  ,pos=1（1自己所在位置）, 1可以贡献的次数即为：(1-(-1))*(4-1) = 6

针对 2可以贡献的次数为：

[3,1,2,4]  left=1, right = 4, 可以贡献的次数即为: (2-1)*(4-2) = 2

 

class Solution {
    public int sumSubarrayMins(int[] arr) {
　　　　 //定义stack1计算每个数字的左侧/右侧小于自己的数字位置
        Stack<Integer> stack1 = new Stack();
        Stack<Integer> stack2 = new Stack();
        int[] preSmaller = new int[arr.length];
        int[] postSmaller = new int[arr.length];
        for(int i=0;i<arr.length;i++){
            while(!stack1.isEmpty() && arr[stack1.peek()] >=arr[i]) 
                stack1.pop();
            preSmaller[i] = stack1.isEmpty() ? -1 : stack1.peek();
            stack1.push(i);
        }
        for(int i=arr.length-1;i>=0;i--){
            while(!stack2.isEmpty() && arr[stack2.peek()] >arr[i]) 
                stack2.pop();
            postSmaller[i] = stack2.isEmpty() ? arr.length : stack2.peek();
            stack2.push(i);
        }
　　　　 //计算结束后
        long sum = 0;
        long mod = (long)1e9 + 7;
        for(int i=0;i<arr.length;i++){
            sum += ((long)(i-preSmaller[i]) * (postSmaller[i]-i) * arr[i])%mod;
            sum %= mod;
        }
        return (int)sum;
    }
}

 

828. Count Unique Characters of All Substrings of a Given String Hard

Let's define a function countUniqueChars(s) that returns the number of unique characters on s.

• For example, calling countUniqueChars(s) if s = "LEETCODE" then "L", "T", "C", "O", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

 Example 1:

Input: s = "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2:

Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.

Example 3:

Input: s = "LEETCODE"
Output: 92

Constraints:

• 1 <= s.length <= 105
• s consists of uppercase English letters only.

同样，bruteforce ，时间复杂度为O(N³) 或者 优化后O(N²)

但如果我们从每个字母的贡献度来考虑的话,比如：

ABCA

第一个A可以贡献的次数为: A,AB,ABC,ABCA

B可以贡献的次数为：AB,B,BC,BCA

class Solution {
    public int uniqueLetterString(String s) {
        int[] left = new int[s.length()];
        int[] right = new int[s.length()];
        int[] lastPos = new int[26];
        Arrays.fill(lastPos, -1);
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            left[i] = lastPos[c-'A'];
            lastPos[c-'A'] = i;
        }
        Arrays.fill(lastPos, s.length());
        for(int i=s.length()-1;i>=0;i--){
            char c = s.charAt(i);
            right[i] = lastPos[c-'A'];
            lastPos[c-'A'] = i;
        }
        int sum = 0;
        for(int i=0;i<s.length();i++){
            sum += (i-left[i])*(right[i]-i);
        }
        return sum;
    }
}

 

标签：arr,907,int,计数,length,828,new,stack2,stack1
From： https://www.cnblogs.com/cynrjy/p/16618334.html