Note for LeetCode in Java (1600+)

Posted on | Edited on | In | | Views:
Symbols count in article: 23k | Reading time ≈ 24 mins.

刷题。祝我好运。

1610. maximum-number-of-visible-points

  • 给一个当事人坐标、可视角度、一系列点的坐标，求这个人在该处旋转360所能看到的最多点数。
  • 以当事人坐标为原点构建极坐标，反正不在意距离，就只保存角度即可。将各点与极坐标轴（可以理解为x正轴）的夹角存入数组并排序，然后利用双指针找delta恰好在可视范围内的，索引相减就知道囊括了多少点了。由于极坐标的夹角是单向的，因此在计算夹角的时候30和300度形成的是270度而不是90度。为了应对这种情况，可以将极坐标再绕一圈，只不过将每个夹角shift 360度，这样就是390 - 300 = 90了。edge case还要考虑有些点恰好就在当事人处。时间O(NlogN)，空间O(N).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
        public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
            if (points == null || points.isEmpty() || location == null || location.isEmpty()) {
                return 0;
            }
            int atSpot = 0;
            List<Double> angles = new ArrayList<>();
            for (List<Integer> point : points) {
                int xDiff = point.get(0) - location.get(0);
                int yDiff = point.get(1) - location.get(1);
                if (xDiff == 0 && yDiff == 0) {
                    atSpot++;
                } else {
                    angles.add(Math.atan2(yDiff, xDiff) * 180 / Math.PI);
                }
            }
            
            Collections.sort(angles);
            List<Double> circular = new ArrayList(angles);
            for (double a : angles) {
                circular.add(a + 360);
            }
            
            int left = 0, right = 0, max = 0;
            while (right < circular.size()) {
                if (circular.get(right) - circular.get(left) > angle) {
                    left++;
                }
                max = Math.max(max, right - left + 1);
                right++;
            }
            return max + atSpot;
        }
    }

1647. minimum-deletions-to-make-character-frequencies-unique

  • 给一个字符串，求需要删除多少个字符才能让其中每个字符的出现次数都是唯一的。

  • 贪心，先统计每个字符出现的次数，然后遍历这些字符的频数，如果这个频数出现过了，那就一直减直到有没有出现过的频数即可。但这个方法不足之处是这个freq是逐位减的，最差情况下可能会达到O(N^2)的时间复杂度.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int minDeletions(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            // count occurance
            int[] bucket = new int[26];
            for (char c : s.toCharArray()) {
                bucket[c - 'a']++;
            }
            int deleteCount = 0;
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < bucket.length; i++) {
                int freq = bucket[i];
                while (set.contains(freq) && freq > 0) {
                    freq--;
                    deleteCount++;
                }
                set.add(freq);
            }
            return deleteCount;
        }
    }

  • 更快捷方法是按照频数排序，从大到小尝试将频数按照递减的规律赋值(如9, 8, 7 ...)，这样最后原字符串长度减去频数之和就是删掉的字符个数了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public int minDeletions(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            // count occurance
            int[] bucket = new int[26];
            for (char c : s.toCharArray()) {
                bucket[c - 'a']++;
            }
            Arrays.sort(bucket);
            int newFreqSum = bucket[25], prevFreq = bucket[25];
            for (int i = 24; i >= 0 && bucket[i] > 0 && prevFreq > 0; i--) {
                prevFreq = Math.min(prevFreq - 1, bucket[i]);
                newFreqSum += prevFreq;
            }
            return s.length() - newFreqSum;
        }
    }

1690. stone-game-vii

  • 给一个数组表示石头堆，A和B每次从两端取石头，所得分数为剩余石头的总和，若两人都是全局最优决策，A先取，A尽可能将二人的分差拉大、B尽可能将二人分差缩小，求A和B的最终分差。
  • 经典miniMax。dp[i][j]表示该玩家的diff值，分别维护A和B的diff。利用prefixSum快速求给定范围内的分数和，若当前是A操作则应取两边取完石头所得分数的最大值、B则是最小值。时间复杂度为O(4 * N^2)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
        public int stoneGameVII(int[] stones) {
            if (stones == null || stones.length == 0) {
                return 0;
            }
            int len = stones.length;
            int[] prefixSum = new int[len];
            prefixSum[0] = stones[0];
            for (int i = 1; i < len; i++) {
                prefixSum[i] = prefixSum[i - 1] + stones[i];
            }
            // alice = 1, bob = 0
            return getDiff(prefixSum, new Integer[len][len][2], 0, len - 1, 1);
        }
        private int getSum(int[] prefixSum, int start, int end) {
            return start > 0 ? prefixSum[end] - prefixSum[start - 1] : prefixSum[end];
        }
        private int getDiff(int[] prefixSum, Integer[][][] dp, int start, int end, int index) {
            if (start == end) {
                return 0;
            }
            if (dp[start][end][index] == null) {
                if (index == 1) {
                    dp[start][end][index] = Math.max(
                        getDiff(prefixSum, dp, start + 1, end, 1 - index) + getSum(prefixSum, start + 1, end), 
                        getDiff(prefixSum, dp, start, end - 1, 1 - index) + getSum(prefixSum, start, end - 1));
                } else {
                    dp[start][end][index] = Math.min(
                        getDiff(prefixSum, dp, start + 1, end, 1 - index) - getSum(prefixSum, start + 1, end), 
                        getDiff(prefixSum, dp, start, end - 1, 1 - index) - getSum(prefixSum, start, end - 1));
                }
            }
            return dp[start][end][index];
        }
    }

1746. maximum-subarray-sum-after-one-operation

  • 给一个int数组，求恰好经过一次平方操作后的最大的subarray之和。
  • DP。对于平方操作每一个元素有两种可能：平方或者不平方；对于subarray操作每一个元素有两种可能：取或者不取。dp[i][0]表示取当前元素且没有经过任何平方操作的最大subarry和，dp[i][1]表示取当前元素且恰好经过一次平方操作的最大subarray和。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0]; dp[0][1] = nums[0] * nums[0];
        int res = dp[0][1];
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + nums[i], nums[i]);   // 继续累加，或断掉重新计算subarray和
            dp[i][1] = Math.max(nums[i] * nums[i], Math.max(dp[i - 1][1] + nums[i], dp[i - 1][0] + nums[i] * nums[i]));
            // 断掉重新以平方数作为新开始，或取平方后累加到尚未平方的前序subarray和，或直接累加到平方过了的前序subarray和
            res = Math.max(res, dp[i][1]);
        }
        return res;
    }

【1802. maximum-value-at-a-given-index-in-a-bounded-array

  • 假设在一个int数组中，要求每个元素都是正数、相邻的数差距最多是1，给定数组长度n，目标索引index，最大数组元素之和maxSum，求满足所有条件下的nums[index]的最大值。
  • nums[index]两翼的元素都可以在O(1)时间内求出，关键是怎么找到这个max的nums[index]。朴素做法是线性搜索，暴力从小到大遍历，最后一个满足所有条件的即为所求。优化的做法是用二分查找在O(logN)内找到最后一个满足条件的值（last occurence）.此外还有一个坑在于在判断是否小于maxSum过程中求和可能越界。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
        public int maxValue(int n, int index, int maxSum) {
            long left = 1, right = maxSum + 1;
            while (left < right) {
                long mid = left + (right - left) / 2;
                if (getSum(mid, index, n) <= maxSum) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return (int) (left - 1);
        }
        private long getSum(long value, long index, long n) {
            long leftLen = index, rightLen = n - index - 1, sum = -value;
            if (value > leftLen) {
                sum += (value - leftLen + value) * (leftLen + 1) / 2;
            } else {
                sum += (1 + value) * value / 2 + (leftLen - value + 1);
            }
            
            if (value > rightLen) {
                sum += (value - rightLen + value) * (rightLen + 1) / 2;
            } else {
                sum += (1 + value) * value / 2 + (rightLen - value + 1);
            }
            return sum;
        }
    }

1806. minimum-number-of-operations-to-reinitialize-a-permutation

  • 假设又一个n个元素的数组（n为偶数），按照如下规则不断地将元素在数组内部挪动（If i % 2 == 0, then arr[i] = perm[i / 2]；If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2]）。求需要多少步能够返回到最初的数组状态。
  • 找规律，既然要求最终回到原点，那不妨倒推index的变化规律。i_old = i_new * 2或者i_old = 2 * (i_new - n / 2) + 1。理论上任何一个i都可以这样推，但由于n >= 2，因此i的值从i = n / 2 = 1开始就能够覆盖所有可能情况。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public int reinitializePermutation(int n) {
            if (n < 2) {
                return 0;
            }
            int retVal = 0, i = 1;
            while (retVal == 0 || i > 1) {
                if (i < n / 2) {
                    i = i * 2;
                } else {
                    i = 2 * (i - n / 2) + 1;
                }
                retVal++;
            }
            return retVal;
        }
    }

1818. minimum-absolute-sum-difference

  • 给两个等长int数组，定义absolute sum difference为同索引的两个元素之差的和，假设可以在第一个数组nums1中至多一个元素为任意nums1中的另一个元素，求最小的ASD.
  • 抽象为给一个nums2中的元素要找出nums1中与他最接近的前后两个元素，立刻想到二分查找/treeSet。可以先将所有元素的diff相加后，逐位尝试将nums1替换为与nums2最接近的两个，看看更新后和diff sum是否更小。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
        private int MOD = (int)Math.pow(10, 9) + 7;
        public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
            if (nums1 == null || nums2 == null || nums1.length != nums2.length) {
                return 0;
            }
            TreeSet<Integer> treeSet = new TreeSet<>();
            int sumDiff = 0, len = nums1.length;
            // NlogN
            for (int i = 0; i < len; i++) {
                treeSet.add(nums1[i]);
                sumDiff = (Math.abs(nums1[i] - nums2[i]) + sumDiff) % MOD;
            }
            
            int minSum = sumDiff;
            for (int i = 0; i < len; i++) {
                if (nums1[i] == nums2[i]) {
                    continue;
                }
                Integer floor = treeSet.floor(nums2[i]), ceiling = treeSet.ceiling(nums2[i]);
                if (ceiling == null) {
                    ceiling = nums1[i];
                }
                if (floor == null) {
                    floor = nums1[i];
                }
                
                int updatedSum = sumDiff - Math.abs(nums1[i] - nums2[i]);
                minSum = Math.min(minSum, Math.min((updatedSum + Math.abs(ceiling - nums2[i])) % MOD,
                                                   (updatedSum + Math.abs(floor - nums2[i])) % MOD));
            }
            return minSum;
        }
    }

1819. number-of-different-subsequences-gcds

  • 给一个正int数组，求他的所有subsequence中所有不同的最大公约数个数。这些int的范围在1 - 200000之间。
  • 所有的subsequence显然不可能全部遍历然后求GCD。既然范围固定，那么所有factor的范围也一定在1 - 200000之间，因此对于每个元素的每个factor可以作标记，标记的内容就是“以当前索引作为因数的所有元素的最大公约数”，这样只要索引内存放的最大公约数就是它本身就说明它至少被两个不同元素作为最大公约数了。时间复杂度为O(N * sqrt(N) * logN)，其中gcd的时间复杂度为logN.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    class Solution {
        public int countDifferentSubsequenceGCDs(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int[] factors = new int[200001];
            for (int num : nums) {
                for (int i = 1; i * i <= num; i++) {
                    if (num % i == 0) {
                        int factor1 = i, factor2 = num / i;
                        if (factors[factor1] == 0) {
                            factors[factor1] = num;
                        } else {
                            factors[factor1] = findGcd(num, factors[factor1]);
                        }
                        if (factors[factor2] == 0) {
                            factors[factor2] = num;
                        } else {
                            factors[factor2] = findGcd(num, factors[factor2]);
                        }
                    }
                }
            }
            
            int count = 0;
            for (int i = 1; i < factors.length; i++) {
                if (factors[i] == i) {
                    count++;
                }
            }
            return count;
        }
        private int findGcd(int a, int b) {
            while (b != 0) {
                int t = a;
                a = b;
                b = t % b;
            }
            return a;
        }
    }

1825. finding-mk-average

  • 假设有一个stream of data，实现一个类允许addElement操作和getMkAvg，其中m表示截取最后出现的m个值、k表示去掉最大的k个和最小的k个元素，求剩余元素的平均值。
  • 暴力方法：add就O(1)无脑加，getMkAvg就排序后求m - 2*k区间的平均值，O(N*logN)。
  • treeMap方法：维护顺序用Queue，维护大小用treeSet（由于set不支持多元素，因此自己用TreeMap实现一个MultiTreeSet）按照区间维护左、中、右三个treeMap，add时从最左边加入，然后根据size是否超标逐层上浮。需要注意除了根据size上浮，还需要判断两两之间的临接元素，例如分别插入1 | 2 | 3之后，插入4时按照size规则是将最久远的1删除得到4 | 2 | 3，这时还需要将两两交界部分swap一下。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    class MKAverage {
        MultiTreeSet left, mid, right;
        int sideSize, midSize, allSize;
        Queue<Integer> q;
        long midSum;
        public MKAverage(int m, int k) {
            left = new MultiTreeSet();
            mid = new MultiTreeSet();
            right = new MultiTreeSet();
            q = new LinkedList<>();
            sideSize = k;
            midSize = m - 2 * k;
            allSize = m;
            midSum = 0L;
        }
        
        public void addElement(int num) {
            q.offer(num);
            left.add(num);
            if (q.size() > allSize) {
                int target = q.poll();
                if (left.contains(target)) {
                    left.remove(target);
                } else if (mid.contains(target)) {
                    mid.remove(target);
                    midSum -= target;
                } else if (right.contains(target)) {
                    right.remove(target);
                }
            }
            if (left.size() > sideSize) {
                int leftMax = left.pollLast();
                mid.add(leftMax);
                midSum += leftMax;
            }
            if (mid.size() > midSize) {
                int midMax = mid.pollLast();
                right.add(midMax);
                midSum -= midMax;
            }
            if (q.size() == allSize) {
                if (left.peekLast() > mid.peekFirst()) {
                    int leftMax = left.pollLast();
                    int midMin = mid.pollFirst();
                    left.add(midMin);
                    mid.add(leftMax);
                    midSum = midSum - midMin + leftMax;
                }
                if (mid.peekLast() > right.peekFirst()) {
                    int midMax = mid.pollLast();
                    int rightMin = right.pollFirst();
                    mid.add(rightMin);
                    right.add(midMax);
                    midSum = midSum - midMax + rightMin;
                }
            }
        }
        
        public int calculateMKAverage() {
            return q.size() == allSize ? (int)(midSum / midSize) : -1;
        }
        
        static class MultiTreeSet {
            private TreeMap<Integer, Integer> treeMap;
            private int totalCount;
            public MultiTreeSet() {
                treeMap = new TreeMap<>();
                totalCount = 0;
            }
            public int size() {
                return totalCount;
            }
            public void add(int num) {
                treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
                totalCount++;
            }
            public boolean contains(int num) {
                return treeMap.containsKey(num);
            }
            public boolean remove(int num) {
                if (!contains(num)) {
                    return false;
                }
                treeMap.put(num, treeMap.get(num) - 1);
                if (treeMap.get(num) == 0) {
                    treeMap.remove(num);
                }
                totalCount--;
                return true;
            }
            public int peekFirst() {
                return treeMap.firstKey();
            }
            public int peekLast() {
                return treeMap.lastKey();
            }
            public int pollFirst() {
                int first = treeMap.firstKey();
                remove(first);
                return first;
            }
            public int pollLast() {
                int last = treeMap.lastKey();
                remove(last);
                return last;
            }
        }
    }
    /**
     * Your MKAverage object will be instantiated and called as such:
     * MKAverage obj = new MKAverage(m, k);
     * obj.addElement(num);
     * int param_2 = obj.calculateMKAverage();
     */

1838. frequency-of-the-most-frequent-element

  • 给一个int数组和一个正数k，假设每一次操作能够任选一个数组元素加1，最多进行k次这个操作，求一波操作后得到的数组的最大frequency。
  • 滑动窗口。操作只能加，等同于在数组给定区间内将所有元素加成max元素，因此做法为将数组排序后滑动窗口，若窗口内元素之和 + k小于最大元素*窗口长度就说明可以继续扩大窗口范围。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int maxFrequency(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            Arrays.sort(nums);
            int left = 0, ans = 1;
            long sum = (long)nums[0];
            for (int right = 1; right < nums.length; right++) {
                sum += (long)nums[right];
                while (sum + k < (long)nums[right] * (right - left + 1)) {
                    sum -= nums[left++];
                }
                ans = Math.max(ans, right - left + 1);
            }
            return ans;
        }
    }
  • 如果不允许用long，那么就要回归到计算diff上面。仍旧是滑动窗口，主角变成右边界最大值和各个元素的diff之和。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public int maxFrequency(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            Arrays.sort(nums);
            int left = 0, ans = 1, currMax = Integer.MAX_VALUE, currDiff = 0;
           for (int right = 0; right < nums.length; right++) {
                if (currMax != nums[right]) {
                    currDiff += (right - left) * (nums[right] - currMax);
                    currMax = nums[right];
                    while (currDiff > k) {
                        currDiff -= (currMax - nums[left++]);
                    }
                }
                ans = Math.max(ans, right - left + 1);
            }
            return ans;
        }
    }

1840. maximum-building-height

  • 假设有n栋楼房，假设第一栋楼房高度为1，相邻的楼房高度只能相差1，此外还给一个数组作为高度限制，求所有n栋楼房的最大高度。
  • 假设给定两处楼房的高度，那么他们之间的所有楼房的最大高度都是确定的。因此考虑从两边分别遍历restriction确定这些位置楼房的最大高度，然后就可以求得两两之间的最大高度了。为了方便计算，手动在最前方插入(1, 0)和(n, inf)，这个即使重复也没有关系。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public int maxBuilding(int n, int[][] restrictions) {
            if (restrictions == null) {
                return 0;
            }
            List<int[]> heights = new ArrayList<>();
            heights.add(new int[]{1, 0});
            for (int[] restriction : restrictions) {
                heights.add(restriction);
            }
            heights.add(new int[]{n, Integer.MAX_VALUE});
            // 按照楼房id从小到大排序
            Collections.sort(heights, (a, b) -> a[0] - b[0]);
            
            // 从右到左递增的情况，忽略最后一个高度
            for (int i = heights.size() - 3; i >= 0; i--) {
                heights.get(i)[1] = Math.min(heights.get(i)[1], heights.get(i + 1)[1] + heights.get(i + 1)[0] - heights.get(i)[0]);
            }
            
            // 从左到右递增的情况
            int ans = 0;
            for (int i = 1; i < heights.size(); i++) {
                heights.get(i)[1] = Math.min(heights.get(i)[1], heights.get(i - 1)[1] + heights.get(i)[0] - heights.get(i - 1)[0]);
                int diffX = heights.get(i)[0] - heights.get(i - 1)[0], diffY = Math.abs(heights.get(i)[1] - heights.get(i - 1)[1]);
                int maxHeight = Math.min(heights.get(i)[1], heights.get(i - 1)[1]) + (diffX + diffY) / 2;
                ans = Math.max(ans, maxHeight);
            }
            return ans;
        }
    }

1851. minimum-interval-to-include-each-query

  • 给一堆闭区间[left, right]，给一些（不重复的）数字，查找包含各个数的所有区间的最小长度，以数组形式返回这些最小长度。
  • 将闭区间排序就能快速找到给定数字的所有区间了，维护一个长度为排序标准的优先队列，为了单向地填充维护区间长度的PQ考虑将query也进行排序，这样就能保证从小的开始查询。这个PQ中还需要存放该区间的结束位置在哪，这样才能知道能否cover给定数字。由于相同长度的区间可能有很多，我们只需要保留最大的结束位置就能知道能否cover当前数字了，因此考虑将PQ存入treemap，key为区间长度、value为区间结束位置。从小到达读query时把所有起始位置小于等于它的区间都存入treemap(PQ)，然后从PQ最前面开始看结束位置是否能cover当前元素。由于有两个排序，时间复杂度为O(nlogn + qlogq)，其中维护treemap也是O(nlogn).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
        public int[] minInterval(int[][] intervals, int[] queries) {
            if (intervals == null || intervals.length == 0 || 
               queries == null || queries.length == 0) {
                return new int[0];
            }
            int[] q = Arrays.copyOf(queries, queries.length);
            Arrays.sort(q);
            Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
            
            TreeMap<Integer, Integer> pq = new TreeMap<>();
            Map<Integer, Integer> resultMap = new HashMap<>();
            int i = 0;
            for (int target : q) {
                while (i < intervals.length && intervals[i][0] <= target) {
                    pq.put(intervals[i][1] - intervals[i][0] + 1, intervals[i][1]);
                    i++;
                }
                while (!pq.isEmpty() && pq.firstEntry().getValue() < target) {
                    pq.pollFirstEntry();
                }
                resultMap.put(target, pq.isEmpty() ? -1 : pq.firstKey());
            }
            int[] ans = new int[queries.length];
            i = 0;
            for (; i < queries.length; i++) {
                ans[i] = resultMap.get(queries[i]);
            }
            return ans;
        }
    }

1856. maximum-subarray-min-product

  • 定义min-product为一段区间内的最小值乘以该区间的和，给一个int数组，求它所有subarray的min-product的最大值。
  • 区间和用prefixSum. 每个元素在某个subarray中都可能是min，因此对于每个元素需要快速知道左边和右边离他最近的小于它的值，这样中间所夹范围就可以求min-product了，尝试将每个元素作为最小值求min-product即可。维护一个left数组存放左边距离该元素最近的、小于它的元素索引，若该元素是最小的，left直接赋值为-1。类似地，维护right，若它已经是最小值了，赋值为数组长度。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    class Solution {
        private int MOD = (int)1e9 + 7;
        public int maxSumMinProduct(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            Deque<Integer> stack = new ArrayDeque<>();
            int[] left = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    left[i] = -1;
                } else {
                    left[i] = stack.peek();
                }
                stack.push(i);
            }
            stack = new ArrayDeque<>();
            int[] right = new int[nums.length];
            for (int i = nums.length - 1; i >= 0; i--) {
                while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    right[i] = nums.length;
                } else {
                    right[i] = stack.peek();
                }
                stack.push(i);
            }
            
            long[] prefixSum = new long[nums.length];
            prefixSum[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                prefixSum[i] = prefixSum[i - 1] + (long)nums[i];
            }
            
            long retVal = 0;
            for (int i = 0; i < nums.length; i++) {
                long sum = left[i] == -1 ? prefixSum[right[i] - 1] : (prefixSum[right[i] - 1] - prefixSum[left[i]]);
                long currProd = (long)nums[i] * sum;
                retVal = Math.max(retVal, currProd);
            }
            return (int)(retVal % MOD);
        }
    }