3494 酿造药水需要的最少时间 **

给你两个长度为 n 和 m 的整数数组 skill 和 mana。有 n 个巫师，要按顺序酿造 m 个药水。每个药水的法力值为 mana[j],第 i 个巫师在第 j 个药水上处理的时间为 skill[i] * mana[j] 。

要确保每个药水完成后，能立即交给下一个巫师开始工作

返回酿造所有药水所需的最短时间。

有点类似流水线问题

84. 柱形图中最大的矩形 **

柱状图中，找出最大面积的矩形，

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int largestRectangleArea(int[] heights) {
        int ans = 0;
        int n = heights.length;
        for(int i = 0;i<n;i++){
            int leftArea = heights[i];
            int rightArea = heights[i];
            for(int j=i+1;j<n&&heights[j]>=heights[i];j++){
                rightArea+=heights[i];
            }
            for(int j=i-1;j>=0&&heights[j]>=heights[i];j--){
                leftArea+=heights[i];
            }
            ans = ans>leftArea+rightArea-heights[i]?ans:leftArea+rightArea-heights[i];
        }
        return ans;
    }
}

1343. 大小为K且平均值大于等于阈值的子数组数目

维护一个定长的滑动窗口，先将长度加到 k，然后重复进一个出一个，要有一个变量存储窗口首部的元素（感觉可以直接根据当前长度 k 进行计算，不用存储）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int sum = 0;
        int ans = 0;
        for(int i=0;i<k;i++)
            sum+=arr[i];
        ans = sum*1.0/k>=threshold?1:0;
        for(int i=k;i<arr.length;i++){
            sum = sum+arr[i]-arr[i-k];
            if(sum*1.0/k>=threshold)
                ans+=1; 
        }
        return ans;

    }
}

2090. 半径为k的子数组平均值

给你一个下标从 0 开始的数组 nums，数组中有 n 个整数，另给一个整数 k

半径为 k 的子数组平均值： nums 中一个以下标 i 为中心且半径为 k 的子数组中所有元素的平均值。如果半径达不到 k ，那么半径为 k 的子数组平均值是 -1

构建一个长度为 n 的数组 avgs，其中 avgs[i] 是以下标 i 为中心的子数组的半径为 k 的子数组平均值。

那么我可以维护一个长度为 2k 的滑动窗口， 然后就和上面一题一摸一样，维护当前滑动窗口元素之和 sum 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n];
        long sum = 0;
        for(int i=0;i<=2*k&&i<n;i++){
            sum+=nums[i];
            if(i<k){
                ans[i]=-1;
                ans[n-i-1]=-1;
            }
        }
        if(k*2+1<=n)
            ans[k] = (int)(sum/(2*k+1));
        for(int i=2*k+1;i<n;i++){
            sum = sum+nums[i]-nums[i-2*k-1];
            ans[i-k] = (int)(sum/(2*k+1));
        }
        return ans;
    }
}

2379. 得到 K 个黑块的最少涂色次数

要最少操作，得到K个连续黑块。那么我们就是要统计长度为 k 的滑动窗口，然后这个窗口里面的黑色块最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumRecolors(String blocks, int k) {
        int bSum = 0;
        int max = -1;
        for(int i=0;i<k;i++){
            if(blocks.charAt(i)=='B')
                bSum+=1;
        }
        max = bSum;
        for(int i=k;i<blocks.length();i++){
            if(blocks.charAt(i-k)=='B')
                bSum-=1;
            if(blocks.charAt(i)=='B')
                bSum+=1;
            max = Math.max(max,bSum);
        }
        return k-max;
    }
}

2841. 几乎唯一子数组的最大和

要找长度为 k 的和最大的子数组，同时要满足这个子数组有 m 个互不相同的元素。

如何知道一个子数组 有 m 个互不相同的元素呢? 我的第一直觉是用一个 Set 来存储。但是有一个问题，删去的元素可能当前窗口里还有，比如说 1,1,1,3 (m=2,k=2)，当遍历到 1,3时 ，先加入1，再删去1，。。好像换一下加入和删除的顺序就可以了。也不行，就算是先删除，那么先删1，再加入3，最后 set 中只有 3 .

看来只能用 map 了，加入一个元素，就使其 v 加 1，如果 v==1 ，就使m-1 ，然后删除一个元素，就使其 v-1 ,如果 v==0，那么设置 m+1 。判断有没有 m 个不同的元素，只需要判断 m<=0 即可。

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 long maxSum(List<Integer> nums, int m, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        long sum = 0;
        long ans = 0;
        for(int i=0;i<k;i++){
            int t = nums.get(i);
            sum+=t;
            map.merge(t,1,(oldVal,newVal)->oldVal+newVal);
            if(map.get(t)==1)
                m-=1;

        }
        if(m<=0)
            ans = sum;
        for(int i=k;i<nums.size();i++){
            int t1 = nums.get(i);
            int t2 = nums.get(i-k);
            sum = sum + t1 -t2;
            map.merge(t2,-1, Integer::sum);
            if(map.get(t2)==0)
                m+=1;
            map.merge(t1,1,Integer::sum);
            if(map.get(t1)==1)
                m-=1;
            
            if(m<=0)
                ans = Math.max(ans,sum);
        }
        return ans;
    }
}

2461. 长度为 K 子数组中的最大和

要求子数组中的所有元素各不相同。这次应该可以使用到集合了。集合的长度应该严格满足等于 k。

其实还是不行，跟上面一样的问题

1423. 可获得的最大点数

每次行动，可以从行的开头或者末尾拿一张卡牌，最终必须正好拿到 k 张卡牌。

每次行动的时候，必须从行的开头或者末尾拿一张卡牌。

选择？如果遍历的话，应该有 2k2^k 个不同的组合。

首先如果 k=1 那么，就只需要知道第一个和最后一个中的较大值。 如果 k=n ，那么就是整个数组。如果是 k=n-1呢？

拿走 k 张，剩下 n-k 张，且需要 k 张最大，然后这 k 张是从首尾取的，那么剩下的卡片必然是连续的。也就是说，目标可以转化为求长度为 n-k 的最小和窗口。

3090. 每个字符最多出现两次的最长字符串

设当前遍历的区间是 left~right,可以知道如果 alpha[right]>2,那么要将left 调整为下一个满足 alpha[right]<=2

3679. 使库存平衡的最少丢弃次数

给你两个整数 w 和 m,以及一个表示第 i 天到达的物品类型 arrivals[i]

操作规则：

  • 物品可保留或被丢弃，物品只能在到达当天被丢弃
  • 对于每一天 i,距离

相当于维护一个长度为 w 的数组，