网站后台上次图片,免费领云服务器,外贸建站seo,网站开发后端用什么目录42. 接雨水思路分析901. 股票价格跨度思路581. 最短无序连续子数组思路一#xff1a;排序双指针思路二#xff1a;单调栈思路三#xff1a;双指针(最省时)42. 接雨水
42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子… 目录42. 接雨水思路分析901. 股票价格跨度思路581. 最短无序连续子数组思路一排序双指针思路二单调栈思路三双指针(最省时) 42. 接雨水
42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例 2 输入height [4,2,0,3,2,5] 输出9 提示 n height.length 0 n 3 * 10^4 0 height[i] 10^5 思路分析
由于这一题方法比较多就专门写了一个 https://blog.csdn.net/qq_42604176/article/details/111053090
901. 股票价格跨度
编写一个 StockSpanner 类它收集某些股票的每日报价并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数从今天开始往回数包括今天。
例如如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。 示例 输入[“StockSpanner”,“next”,“next”,“next”,“next”,“next”,“next”,“next”], [[],[100],[80],[60],[70],[60],[75],[85]] 输出[null,1,1,1,2,1,4,6] 解释 首先初始化 S StockSpanner()然后 S.next(100) 被调用并返回 1 S.next(80) 被调用并返回 1 S.next(60) 被调用并返回 1 S.next(70) 被调用并返回 2 S.next(60) 被调用并返回 1 S.next(75) 被调用并返回 4 S.next(85) 被调用并返回 6。 注意 (例如) S.next(75) 返回 4因为截至今天的最后 4 个价格 (包括今天的价格 75) 小于或等于今天的价格。
思路
仍然是单调栈的思路构造一个单调递减栈。 1、如果当前栈为空输入元素在原数组中的下标压入栈中。 获取该元素左边极大值的坐标此时栈为空说明左边没有比该元素还小的元素所以左边极大值坐标就是不存在填-1(不能填0) 然后返回长度就是当前元素在原数组中下标 - 左极大值坐标。 可以想象一下如果左边极大值不存在的时候我们填入0而当前输入元素正好是第0个元素那么显然结果就是0 - 0 0 不符合答案1。 2、如果当前栈不为空并且栈顶元素小于等于输入元素。 此时根据题目要求小于或等于今天价格的最大连续日数我们必须要找到大于今日价格才能停止寻找所以仍然需要回撤操作。 直到栈为空或者栈顶元素大于今日价格才停止回撤。 如果栈为空说明左边没有比该元素还小的元素所以左边极大值坐标就是不存在填-1(不能填0) 如果栈不为空左极大值坐标就是当前栈顶元素坐标。 最后将今日 - 左极大值日期就是结果
和之前系列中有的操作还是相似的例如栈中记录的不是元素而是该元素在原数组中的下标。 对于栈顶元素与当前元素的比较仍然是需要结合题意列出三种可能当前元素 、 、 st.back()找到符合题意的出栈标准
class StockSpanner {
private:vectorint input;vectorint st;
public:StockSpanner() {}int next(int price) {//输入一个price,input数组又多了一个元素input.emplace_back(price);//该元素为input数组末尾int now_index input.size() - 1;//如果此时栈为空说明它左边没有值while(!st.empty() input[st.back()] price){st.pop_back();}//获取该元素左边极大值的下标如果栈为空的话说明没有那么left_max就是-1如果不为空返回栈顶int left_max_index;if(st.empty()) left_max_index -1;else left_max_index st.back();//当前元素入栈st.push_back(now_index);return (now_index - left_max_index);}
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj new StockSpanner();* int param_1 obj-next(price);*/581. 最短无序连续子数组
给定一个整数数组你需要寻找一个连续的子数组如果对这个子数组进行升序排序那么整个数组都会变为升序排序。 你找到的子数组应是最短的请输出它的长度。 示例 1: 输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序那么整个表都会变为升序排序。 说明 : 输入的数组长度范围在 [1, 10,000]。 输入的数组可能包含重复元素 所以升序的意思是。 思路一排序双指针
先排序然后将排序后的数组与原数组进行比对(从左到右、从右到左)。 找到左右边界然后最后的结果就是左右边界差值1. 当然还要考虑特殊情况原数组本身是单调递增或递减的这样我们就不能对左右边界进行更新。 但是我们知道单调的结果无非是0(单调递增不需要重新排序)和nums.size()单调递减需要将整个数组都排序.
class Solution {
public:int findUnsortedSubarray(vectorint nums) {vectorint _new nums;sort(_new.begin(),_new.end());int left_index -1;int right_index -1;//双指针left、right从两边向中间遍历for(int left 0; left nums.size(); left){if(nums[left] ! _new[left]){left_index left;break;}}for(int right nums.size() - 1; right 0; right--){if(nums[right] ! _new[right]){right_index right;break;}}//如果是单调递增,不需要修改返回0if(left_index -1) return 0;//如果是单调递减返回整个长度if(right_index -1) return nums.size();return (right_index - left_index 1);}
};思路二单调栈 背后的思想仍然是选择排序我们需要找到无序子数组中最小元素和最大元素分别对应的正确位置。 来求我们需要的无序子数组的边界。 使用栈从头遍历nums数组 1、如果遇到的数组大小一直升序的我们就不断把对应的下标压入栈中目的这些元素目前都是出于正确的位置上 2、一旦当前数字比栈顶元素小那么我们知道nums[j]一定不在正确的位子上 3、既然这样我们就需要找到nums[j]的正确位置 不断将栈顶元素弹出知道栈顶元素比nums[j]假设此刻栈顶元素对应的下标是k那么我们知道nums[j]的正确下标应该是k1 4、重复上述过程直到遍历完整个数组这样我们可以找到最小的k它也是无序子数组的左边界。 5、类似的我们逆序遍历一遍nums数组来找到无序子数组的右边界。这一次我们将降序的元素压入栈中。 6、如果遇到一个升序的元素不断将栈顶元素弹出直到找到一个更大的元素以此找到无序子数组的右边界 class Solution {
public:int findUnsortedSubarray(vectorint nums) {vectorint st;int left nums.size() - 1;int right 0;for(int i 0; i nums.size(); i){while(!st.empty() nums[i] nums[st.back()]){left min(left,st.back()); st.pop_back();}st.emplace_back(i);}st.clear();for(int i nums.size() - 1; i 0; i--){while(!st.empty() nums[i] nums[st.back()]){right max(right,st.back()); st.pop_back();}st.emplace_back(i);}return right - left 0 ? right - left 1 : 0;}
};思路三双指针(最省时)
这一题的双指针解法和接雨水的双指针思想有一定相似性 leetcode 42. 接雨水 思考分析(暴力、动态规划、双指针、单调栈) 我们要做的是找到无序数组的上下界。 运用到本题就是下面两个想法: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/shi-jian-chao-guo-100de-javajie-fa-by-zackqf/ https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/jian-dan-zhi-guan-de-shuang-zhi-zhen-fa-by-sillywo/ 无序子数组中最小元素的正确位置可以决定左边界最大元素的正确位置可以决定右边界。 寻找右边界 从左往右遍历用max记录遍历过的最大值如果max大于当前nums[i]说明nums[i]的位子不正确属于需要排序的数组所以右边界就需要更新为i 如果nums[i]大于max更新max继续往右检查是否有元素比更新之后的max要小最终可以找到需要排序的数组的右边界右边界之后的元素都大于max。 寻找左边界 从右向左遍历yongmin记录当前遍历过的最小值如果min小于当前nums[i]说明nums[i]的位子不正确属于需要排序的数组所以更新左边界 如果nums[i]小于min更新min继续往左检查是否有元素比更新之后的min要大最终可以找到需要排序的数组的左边界左边界之前的元素都小于min
class Solution {
public:int findUnsortedSubarray(vectorint nums) {//特判int n nums.size();if (n 1) {return 0;}//从右到左找下界从左到右找上界int left n - 2, right 1; int curMin nums[n - 1], curMax nums[0];int up 0, down 1;//升序时移动 curMin 和 curMax//逆序时移动 down 和 up//不论顺序如何双指针 left 和 rigt 一直保持移动while (left 0 right n) {if (nums[left] curMin){down left;}else {curMin nums[left];}left--;if (nums[right] curMax) {up right;}else {curMax nums[right];}right;}return up - down 1;}
};单调栈暂时就刷到这儿接下来继续刷双指针的题目吧。
