众筹平台网站建设,如何做问卷调查网站,网络安全培训机构哪家好,什么公司做网站会提供源代码单调栈系列复习 每日温度未看解答自己编写的青春版重点题解的代码日后再次复习重新写 下一个更大元素 I未看解答自己编写的青春版重点题解的代码日后再次复习重新写 下一个更大元素II未看解答自己编写的青春版重点题解的代码日后再次复习重新写 接雨水未看解答自己编写的青春版… 单调栈系列复习 每日温度未看解答自己编写的青春版重点题解的代码日后再次复习重新写 下一个更大元素 I未看解答自己编写的青春版重点题解的代码日后再次复习重新写 下一个更大元素II未看解答自己编写的青春版重点题解的代码日后再次复习重新写 接雨水未看解答自己编写的青春版重点题解的代码按题解风格重写日后再次复习重新写 柱状图中最大的矩形未看解答自己编写的青春版本题计算矩形面积的方式依旧按照上一题接雨水的思路采取横向计算的方式对于当前遍历的位置 i 取当前位置的高度为合并矩形的高度向左向右遍历找到左右两边第一个比此高度底的位置面积就等于高X宽。卡哥的双指针法竟然不超时为什么明白了在循环找左右临近最小时不需要一个下标一个下标地去遍历可以利用已经算好的值进行跳跃这道题因为必须横向计算面积没有列向计算的方法所以我认为没有像上一题接雨水那样具有显著风格的双指针方法。单调栈方法这道题因为要求左右最小临近所以是递减栈。这道题的边界情况不好处理我觉得左边的情况可以通过while里加判断解决。右边的情况目前我认为只能在for循环结束后单独再去弹出栈来计算了。我感觉不如对heights数组左右加0。看看卡哥的写法 重点题解的代码啊哈也是通过前后补0做的合理。 日后再次复习重新写 一段用于复制的标题未看解答自己编写的青春版重点题解的代码日后再次复习重新写 一段用于复制的标题未看解答自己编写的青春版重点题解的代码日后再次复习重新写 一段用于复制的标题未看解答自己编写的青春版重点题解的代码日后再次复习重新写 每日温度
未看解答自己编写的青春版
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:n len(temperatures)stack [0]res [0]*nfor i in range(1,n):while stack ! [] and temperatures[i] temperatures[stack[-1]] :idx stack.pop()res[idx] i-idxstack.append(i)return res重点
每日温度
1、对比用while
2、单调栈里存下标即可
3、求右边第一个更大所以是单调递增栈指的是从栈顶到栈底顺序是单增栈顶是弹出和加入元素的位置。
题解的代码
日后再次复习重新写
下一个更大元素 I
未看解答自己编写的青春版
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:n len(nums2)res [-1]*n# stack还是得存下标存数不方便索引到res结果数组stack [0]for i in range(1,n):while stack ! [] and nums2[i] nums2[stack[-1]] :idx stack.pop()res[idx] nums2[i]stack.append(i)m len(nums1)result [-1]*mfor i in range(m):temp nums2.index(nums1[i])result[i] res[temp]return result重点
同上一题。找索引用 list.index()
下一个更大元素 I
题解的代码
日后再次复习重新写
下一个更大元素II
未看解答自己编写的青春版
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:n len(nums)res [-1]*nstack [0]for i in range(1,2*n):temp i % nwhile stack ! [] and nums[temp] nums[stack[-1]] :j stack.pop()# 注意看我们对每个进入stack单调栈的元素都做了对n的取模处理# 所以这里pop出来的 j 一定是好的不需要经过处理就可以对结果数组赋值res[j] nums[temp]stack.append(temp)return res
重点
本题需要处理的就是循环数组的情况。
朴实的想法是把目标数组复制一倍将目标数组扩容为两倍然后对这个两倍的数组做最原始的单调栈。
可以进一步优化在索引循环时循环到 2*n , 但是对于每个 i 对 i 进行对数组长度 n 的取模操作。
题解的代码
日后再次复习重新写
接雨水
未看解答自己编写的青春版
class Solution:def trap(self, height: List[int]) - int:total 0n len(height)# 栈里放的是索引stack [0]for i in range(1,n): temp 0while stack ! [] and height[i] 0 and height[i] height[stack[-1]] :j stack.pop()total (height[j]-temp)*(i-j-1)temp height[j]# 这个判断是为了处理中间有矮柱或者空的情况但是是我根据错误示例发现的没什么道理啊# 简单举例为[4,2,1,3] [4,0,0,3] 不加下面的判断就会漏掉4和3之间的部分if stack ! [] and height[i] height[stack[-1]] :total (height[i]-temp)*(i-stack[-1]-1)if height[i] 0 :stack.append(i)return total重点
这题要看题解自己写的代码中加入的一段逻辑是为了AC而加的如果不是题目有错误示例我想不到。
接雨水
还是觉得卡哥的题解给的方法是自然的按我的方法第一次确实想不到这种要单独处理的情况。而且不让0入栈是比较牵强的。 本题还有一个要注意的是如果两个数值相等怎么处理照常入栈顶替掉前一个
题解的代码
class Solution:def trap(self, height: List[int]) - int:# 单调栈单调栈是按照 行 的方向来计算雨水从栈顶到栈底的顺序从小到大通过三个元素来接水栈顶栈顶的下一个元素以及即将入栈的元素雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1因为只求中间宽度# stack储存index用于计算对应的柱子高度stack [0]result 0for i in range(1, len(height)):# 情况一if height[i] height[stack[-1]]:stack.append(i)# 情况二# 当当前柱子高度和栈顶一致时左边的一个是不可能存放雨水的所以保留右侧新柱子# 需要使用最右边的柱子来计算宽度elif height[i] height[stack[-1]]:stack.pop()stack.append(i)# 情况三else:# 抛出所有较低的柱子while stack and height[i] height[stack[-1]]:# 栈顶就是中间的柱子储水槽就是凹槽的地步mid_height height[stack[-1]]stack.pop()if stack:right_height height[i]left_height height[stack[-1]]# 两侧的较矮一方的高度 - 凹槽底部高度h min(right_height, left_height) - mid_height# 凹槽右侧下标 - 凹槽左侧下标 - 1: 只求中间宽度w i - stack[-1] - 1# 体积高乘宽result h * wstack.append(i)return result# 单调栈压缩版
class Solution:def trap(self, height: List[int]) - int:stack [0]result 0for i in range(1, len(height)):while stack and height[i] height[stack[-1]]:mid_height stack.pop()if stack:# 雨水高度是 min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度h min(height[stack[-1]], height[i]) - height[mid_height]# 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1w i - stack[-1] - 1# 累计总雨水体积result h * wstack.append(i)return result按题解风格重写
class Solution:def trap(self, height: List[int]) - int:total 0n len(height)# 栈里放的是索引stack [0]for i in range(1,n): while stack ! [] and height[i] height[stack[-1]] :mid stack.pop()if stack ! []:left stack[-1]total (min(height[left],height[i])-height[mid])*(i-left-1)stack.append(i)return total日后再次复习重新写
柱状图中最大的矩形
未看解答自己编写的青春版
没有思路主要难点在于不知道怎样计算最大矩形面积合适。包括上一道题一样一开始也是不晓得怎样计算雨水面积合适比如上一道题按照单调栈计算是按照行来计算的。
本题计算矩形面积的方式依旧按照上一题接雨水的思路采取横向计算的方式对于当前遍历的位置 i 取当前位置的高度为合并矩形的高度向左向右遍历找到左右两边第一个比此高度底的位置面积就等于高X宽。
单调栈没思路的时候先用暴力解法试试。
暴力法超时
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxarea 0n len(heights)for i in range(n):h heights[i]left i-1right i1while left -1 :if heights[left] heights[i] :breakleft - 1while right n :if heights[right] heights[i] :breakright 1temp h * (right-left-1)maxarea max(maxarea,temp)return maxarea DP法二维数组提前存储每个位置的第一个左边小于当前高度的下标第一个右边小于当前高度的下标。超时。在本题中DP法和双指针法相同了DP也无法用递推公式都是用两个一维数组去提前存储而且都需要循环去搜索。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxarea 0n len(heights)dp [[0]*2 for _ in range(n)]dp[0][0] -1dp[n-1][1] n# 注意本题与前一题接雨水的不同前一题因为在用暴力法(DP双指针)都是采用列向计算# 所以在计算左右临近最大时可以使用迭代# 本题因为是求左右临近最小用提前记忆的方法依然需要循环for i in range(1,n):j iwhile j 0 and heights[i] heights[j-1]:j j-1dp[i][0] j-1for i in range(n-2,-1,-1):j iwhile j n-1 and heights[i] heights[j1]:j j1dp[i][1] j1for i in range(n):h heights[i]left dp[i][0]right dp[i][1] temp h * (right-left-1)maxarea max(maxarea,temp)return maxarea
卡哥的双指针法竟然不超时为什么
class Solution:def largestRectangleArea(self, heights: List[int]) - int:size len(heights)# 两个DP数列储存的均是下标indexmin_left_index [0] * sizemin_right_index [0] * sizeresult 0# 记录每个柱子的左侧第一个矮一级的柱子的下标min_left_index[0] -1 # 初始化防止while死循环for i in range(1, size):# 以当前柱子为主心骨向左迭代寻找次级柱子temp i - 1while temp 0 and heights[temp] heights[i]:# 当左侧的柱子持续较高时尝试这个高柱子自己的次级柱子DPtemp min_left_index[temp]# 当找到左侧矮一级的目标柱子时min_left_index[i] temp# 记录每个柱子的右侧第一个矮一级的柱子的下标min_right_index[size-1] size # 初始化防止while死循环for i in range(size-2, -1, -1):# 以当前柱子为主心骨向右迭代寻找次级柱子temp i 1while temp size and heights[temp] heights[i]:# 当右侧的柱子持续较高时尝试这个高柱子自己的次级柱子DPtemp min_right_index[temp]# 当找到右侧矮一级的目标柱子时min_right_index[i] tempfor i in range(size):area heights[i] * (min_right_index[i] - min_left_index[i] - 1)result max(area, result)return result明白了在循环找左右临近最小时不需要一个下标一个下标地去遍历可以利用已经算好的值进行跳跃
在上面原代码的基础上进行的修改但是由于上面那一版没想到这些用的下标是和 j-1 / j1 比较的简直是下标灾难
这个代码能过但是时间和空间上只打败了 5% 。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxarea 0n len(heights)dp [[0]*2 for _ in range(n)]dp[0][0] -1dp[n-1][1] n# 注意本题与前一题接雨水的不同前一题因为在用暴力法(DP双指针)都是采用列向计算# 所以在计算左右临近最大时可以使用迭代# 本题因为是求左右临近最小用提前记忆的方法依然需要循环for i in range(1,n):j i# 下标灾难while j 0 and heights[i] heights[j-1]:# index要减一dp出来的值要加一因为上面的判断是和减一的位置判断的j dp[j-1][0]1dp[i][0] j-1for i in range(n-2,-1,-1):j iwhile j n-1 and heights[i] heights[j1]:# index要加一dp出来的值要减一因为上面的判断是和加一的位置判断的j dp[j1][1]-1dp[i][1] j1for i in range(n):h heights[i]left dp[i][0]right dp[i][1] temp h * (right-left-1)maxarea max(maxarea,temp)return maxarea 不用该死的 j-1 / j1 了重新更改下标
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxarea 0n len(heights)dp [[0]*2 for _ in range(n)]dp[0][0] -1dp[n-1][1] n# 注意本题与前一题接雨水的不同前一题因为在用暴力法(DP双指针)都是采用列向计算# 所以在计算左右临近最大时可以使用迭代# 本题因为是求左右临近最小用提前记忆的方法依然需要循环for i in range(1,n):j i-1while j -1 and heights[i] heights[j]: j dp[j][0]dp[i][0] jfor i in range(n-2,-1,-1):j i1while j n and heights[i] heights[j]: j dp[j][1]dp[i][1] jfor i in range(n):h heights[i]left dp[i][0]right dp[i][1] temp h * (right-left-1)maxarea max(maxarea,temp)return maxarea 更改后下标看起来顺眼多了但是还是都只打败了5%why ?
将二维dp数组拆为了两个一维数组。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxarea 0n len(heights)# 初始化一起做了dp1 [-1]*ndp2 [n]*n# 注意本题与前一题接雨水的不同前一题因为在用暴力法(DP双指针)都是采用列向计算# 所以在计算左右临近最大时可以使用迭代# 本题因为是求左右临近最小用提前记忆的方法依然需要循环for i in range(1,n):j i-1while j -1 and heights[i] heights[j]: j dp1[j]dp1[i] jfor i in range(n-2,-1,-1):j i1while j n and heights[i] heights[j]: j dp2[j]dp2[i] jfor i in range(n):h heights[i]left dp1[i]right dp2[i]temp h * (right-left-1)maxarea max(maxarea,temp)return maxarea 啪的一下很快啊就打败40%了
这道题因为必须横向计算面积没有列向计算的方法所以我认为没有像上一题接雨水那样具有显著风格的双指针方法。
单调栈方法这道题因为要求左右最小临近所以是递减栈。
这道题的边界情况不好处理我觉得左边的情况可以通过while里加判断解决。右边的情况目前我认为只能在for循环结束后单独再去弹出栈来计算了。我感觉不如对heights数组左右加0。看看卡哥的写法
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxarea 0# 这道题的边界情况不好处理我觉得左边的情况可以通过while里加判断解决# 右边的情况目前我认为只能在for循环结束后单独再去弹出栈来计算了# 我感觉不如对heights数组左右加0heights [0]heights[0]n len(heights)stack [0]for i in range(1,n):while stack ! [] and heights[i] heights[stack[-1]]:temp stack.pop()if stack ! [] :left stack[-1]j heights[temp]*(i-left-1)maxarea max(maxarea,j)stack.append(i)return maxarea重点
接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。
这里就涉及到了单调栈很重要的性质就是单调栈里的顺序是从小到大还是从大到小。
在接雨水 (opens new window)中单调栈从栈头元素从栈头弹出到栈底的顺序应该是从小到大的顺序。
因为本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序应该是从大到小的顺序。
题解的代码
啊哈也是通过前后补0做的合理。
# 单调栈
class Solution:def largestRectangleArea(self, heights: List[int]) - int:# Monotonic Stack找每个柱子左右侧的第一个高度值小于该柱子的柱子单调栈栈顶到栈底从大到小每插入一个新的小数值时都要弹出先前的大数值栈顶栈顶的下一个元素即将入栈的元素这三个元素组成了最大面积的高度和宽度情况一当前遍历的元素heights[i]大于栈顶元素的情况情况二当前遍历的元素heights[i]等于栈顶元素的情况情况三当前遍历的元素heights[i]小于栈顶元素的情况# 输入数组首尾各补上一个0与42.接雨水不同的是本题原首尾的两个柱子可以作为核心柱进行最大面积尝试heights.insert(0, 0)heights.append(0)stack [0]result 0for i in range(1, len(heights)):# 情况一if heights[i] heights[stack[-1]]:stack.append(i)# 情况二elif heights[i] heights[stack[-1]]:stack.pop()stack.append(i)# 情况三else:# 抛出所有较高的柱子while stack and heights[i] heights[stack[-1]]:# 栈顶就是中间的柱子主心骨mid_index stack[-1]stack.pop()if stack:left_index stack[-1]right_index iwidth right_index - left_index - 1height heights[mid_index]result max(result, width * height)stack.append(i)return result# 单调栈精简
class Solution:def largestRectangleArea(self, heights: List[int]) - int:heights.insert(0, 0)heights.append(0)stack [0]result 0for i in range(1, len(heights)):while stack and heights[i] heights[stack[-1]]:mid_height heights[stack[-1]]stack.pop()if stack:# area width * heightarea (i - stack[-1] - 1) * mid_heightresult max(area, result)stack.append(i)return result
日后再次复习重新写
一段用于复制的标题
未看解答自己编写的青春版
重点
题解的代码
日后再次复习重新写
一段用于复制的标题
未看解答自己编写的青春版
重点
题解的代码
日后再次复习重新写
一段用于复制的标题
未看解答自己编写的青春版
重点
题解的代码
日后再次复习重新写
