网站开发的总结与展望,给村里做网站,百度合作推广,上海公司网站制作价格Tag
【单调栈】【暴力枚举】【数组】【2024-03-19】 题目来源
1793. 好子数组的最大分数 解题思路
本题和 84. 柱状图中最大的矩形 一样#xff0c;计算的都是最大矩形的面积。只不过多了一个约束#xff1a;矩形必须包含下标 k。
以下的方法一和方法二是 84. 柱状图中最…Tag
【单调栈】【暴力枚举】【数组】【2024-03-19】 题目来源
1793. 好子数组的最大分数 解题思路
本题和 84. 柱状图中最大的矩形 一样计算的都是最大矩形的面积。只不过多了一个约束矩形必须包含下标 k。
以下的方法一和方法二是 84. 柱状图中最大的矩形 的解法。我将在方法二中增加一个判断条件即可解答本题。
方法一暴力枚举
思路
为了找出柱状图中最大的矩形我们可以枚举矩形的宽和高。
如果我们枚举「宽」我们需要用到两层循环来固定矩形的边界并在矩形的边界中找出最小的高度。这样的操作总的时间复杂度为 O ( n 2 ) O(n^2) O(n2) n n n 为数组 heights 的高度对于本题 1 0 5 10^5 105 的数据规模一定超时。
如果我们枚举「高」需要将数组 heights 中的每一个高度 heights[i] 作为矩形的高并在这个高度左侧和右侧分别找到 最近的高度小于 heights[i] 的柱子这两个柱子之间不包括本身的所有柱子高度均小于 heights就是 i 能扩展的最远距离。 这样操作总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)也会超时。
方法二单调栈
思路
方法二就是将方法一种枚举「高」当中的找到 “最近的高度小于 heights[i] 的柱子” 利用单调栈的方法先计算出来从来降低时间复杂度。
维护两个数组 left 和 rightleft[i] 和 right[i] 分别表示柱子 i 左侧且最近的小于其高度的柱子和柱子 i 右侧且最近的小于其高度的柱子。这样以 heighet[i] 为高度的矩形宽度为 r i g h t [ i ] − 1 − ( l e f t [ i ] 1 ) 1 r i g h t [ i ] − l e f t [ i ] − 1 right[i] - 1 - (left[i] 1) 1 right[i] - left[i] - 1 right[i]−1−(left[i]1)1right[i]−left[i]−1
首先定义一个单调栈 mono_stack 用来存放柱子在数组中的位置接着从前往后枚举数组 heights 来更新 left 以及单调栈 mono_stack
将栈顶的元素与当前枚举的元素值 heights[i] 比较如果栈非空并且栈顶的元素值大于或者等于 heights[i]就出栈直到栈为空或者找到比 heights[i] 小的栈中元素如果栈为空了说明 heights[i] 左侧没有比它小的元素更新left[i] -1否则就是找到了heights[i] 左侧比它小的元素将 nums2[i] 加入栈中。
按照以上操作可以计算出数组 left同理可以得到 right。
最后依次枚举数组 heights 中的高度计算以每个高度为矩形的高的最大值。因为题目要求 “好子数组中间必须包含下标 k”即矩形必须包含下标 k于是需要增加一条判断left[i] k k right[i]在该条件成立的情况下计算矩形的最大面积即本题的好子数组的最大可能分数。
实现代码
class Solution {
public:int maximumScore(vectorint heights, int k) {int n heights.size();vectorint left(n), right(n);stackint mono_stack;for (int i 0; i n; i) {while (!mono_stack.empty() heights[mono_stack.top()] heights[i]) {mono_stack.pop();}left[i] mono_stack.empty() ? -1 : mono_stack.top();mono_stack.push(i);}mono_stack stackint();for (int i n-1; i 0; --i) {while(!mono_stack.empty() heights[mono_stack.top()] heights[i]) {mono_stack.pop();}right[i] mono_stack.empty() ? n : mono_stack.top();mono_stack.push(i);}int res 0;for (int i 0; i n; i) {if (left[i] k k right[i])res max(res, (right[i] - left[i] - 1) * heights[i]);}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组 heights 的高度。
空间复杂度 O ( n ) O(n) O(n)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
