一.643. 子数组最大平均数 I
代码
- Go
func findMaxAverage(nums []int, k int) float64 { n:=len(nums) maxvalue := float64(math.MinInt64) l:=0 sum:=0 for r:=0;r<n;r++{ sum=sum+nums[r] if r-l+1==k{ maxvalue=math.Max(maxvalue,float64(sum)/float64(k)) sum=sum-nums[l] l++ } } return maxvalue }
- cpp
double findMaxAverage(vector<int>& nums, int k) { int n = nums.size(); double maxvalue = INT_MIN; int l = 0; int sum = 0; for (int r = 0; r < n; r++) { sum += nums[r]; if (r - l + 1 == k) { maxvalue = max(maxvalue, static_cast<double>(sum) / k); sum -= nums[l]; l++; } } return maxvalue; }
二.1052. 爱生气的书店老板
思路说明
这道题刚开始看,其实让人感到云里雾里的(博主刚开始写的时候给整了半天没看懂肺都快气炸了,差点和这个书店老板一样了,呜呜呜),但是看懂题目以后思路还是比较清晰的:
- 首先我们现将所有不生气的时间对应的顾客数提取出来,因为这部分肯定是算入结果的,然后将它们置为0
- 然后现在的问题就被我们转化为生气的时候这个连续
minutes
分钟不生气 所对应的子数组最大值是多少,用滑动窗口求解即可。
代码
- Go
func maxSatisfied(customers []int, grumpy []int, minutes int) int { n:=len(customers) res:=0 for i:=0;i<n;i++{ if grumpy[i]!=1{ res=res+customers[i] customers[i]=0 } } l:=0 sum:=0 maxsum:=math.MinInt for r:=0;r<n;r++{ sum+=customers[r] if r-l+1==minutes{ maxsum=max(maxsum,sum) sum-=customers[l] l++ } } return res+maxsum } func max(a,b int) int{ if a>b{ return a } return b }
- Cpp
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) { int n = customers.size(); int res = 0; for (int i = 0; i < n; i++) { if (grumpy[i] != 1) { res += customers[i]; customers[i] = 0; } } int l = 0; int sum = 0; int maxsum = INT_MIN; for (int r = 0; r < n; r++) { sum += customers[r]; if (r - l + 1 == minutes) { maxsum = max(maxsum, sum); sum -= customers[l]; l++; } } return res + maxsum; }