828. 统计子串中的唯一字符 (opens new window)

1.贡献法+哈希

思路：考虑单个字符对答案的贡献值，而不去找出所有的子串。

这里计算单个字符的贡献值采用正难则反的方式，字符c的贡献值=所有字串数目 - 不包含字符c的字串数目。

class Solution {
    public int uniqueLetterString(String s) {
        int res = 0;
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            List<Integer> list = map.get(c);
            if (!map.containsKey(c)) {
                list = new ArrayList<>();
                map.put(c, list);
            }
            list.add(i);
        }
        for (Character c : map.keySet()) {
            List<Integer> list = map.get(c);
            for (int i = 0; i < list.size(); i++) {
                int pre = i == 0 ? -1 : list.get(i - 1);
                int suff = i == list.size() - 1 ? s.length() : list.get(i + 1);

                int sum = (suff - pre) * (suff - pre - 1) / 2;
                int left = (list.get(i) - 1 - pre - 1 + 2) * (list.get(i) - pre - 1) / 2;
                int right = (suff - 1 - (list.get(i) + 1) + 2) * (suff - 1 - (list.get(i) + 1) + 1) / 2;
                int devote = sum - left - right;
                res += devote;
            }
        }
        return res;
    }
}

907. 子数组的最小值之和 (opens new window)

1.贡献法+单调栈

通过单调栈找到第i个元素作为最小值的最大子数组左右边界。

class Solution {
    public int sumSubarrayMins(int[] arr) {
        long res = 0;
        int mod = 1000000007;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                Integer pop = stack.pop();
                int last = stack.size() == 0 ? 0 : stack.peek()+1;
                res =(res+1l*arr[pop] * (pop - last + 1) * (i - pop )%mod)%mod;
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            int last = stack.size() == 0 ? 0 : stack.peek() + 1;
            res =(res+ 1l*arr[pop] * (pop - last + 1) * (arr.length - pop)%mod)%mod;
        }
        return (int)res;
    }
}