做报告的网站,python代码网站,做的网站怎么放到域名,简述建设一个网站的过程所有题目均来自于LeetCode#xff0c;刷题代码使用的Python3版本 单调栈
通常针对一维数组的问题#xff0c;如果需要寻找一个元素右边或者左边第一个比自己大或者小的元素的位置#xff0c;就可以使用单调栈#xff0c;时间复杂度为O(n)
单调栈的本质是空间换时间#… 所有题目均来自于LeetCode刷题代码使用的Python3版本 单调栈
通常针对一维数组的问题如果需要寻找一个元素右边或者左边第一个比自己大或者小的元素的位置就可以使用单调栈时间复杂度为O(n)
单调栈的本质是空间换时间 遍历的过程中需要使用一个栈记录右边第一个比当前元素高的值。优点是整个数组只需要遍历一次。
使用单调栈需要明确的几点
单调栈中存放的元素是什么单调栈里的元素是递增还是递减
单调栈中的元素可以是递增的也可以是递减的具体需要看题目的需求。
单调栈中存放的元素最好是下标这样具有更好的泛型
练习题
739、每日温度 使用单调栈的方式从前往后进行遍历
栈中的元素从栈底到栈顶对应下标的值是递减的直到找到一个比栈顶元素大的值然后出栈。
栈中存放的是元素的下标如果出现一个新的元素比栈中元素都要大的时候就对栈中元素进行循环遍历将其对应的res值修改为当前元素的下标和栈中存放的值的差值这就是最终结果到最后一个元素的时候因为初始化结果列表中元素值都是0故不需要进行修改。
初始化答案res为全0的列表这样可以防止后面的元素没有下一个更大的元素当然这一点要根据题目的要求来因为有些题目会赋值为-1。
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:res [0] * len(temperatures)st []# 从前往后进行遍历for index, temp in enumerate(temperatures):# st不为空且温度大于栈顶元素while st and temperatures[st[-1]] temp:j st.pop()# 题目中问的是下一个更高温度出现在几天之后 因此用下标之差表示即可res[j] index - jst.append(index)return res496、下一个更大元素I 直接寻找
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:res [-1]*len(nums1)# 寻找下一个更大的元素for index,n1 in enumerate(nums1):startindex nums2.index(n1)for n in nums2[startindex1:]:if nn1:res[index] nbreakreturn res使用单调栈
题目中有**【需要寻找最近一个比其大的元素】** 这样的字眼就可以使用 【单调栈】
本题需要注意的是题目中存在两个数组寻找第一个数组在第二个数组元素中下一个比对应元素大的元素。题目中说了两个数组中是没有重复元素的可以采用单调栈哈希表的方式进行解决。
单调栈解决的是nums2中每个元素对应的下一个比其大的元素
哈希表解决的是用来存储每个元素对应的下一个元素值这样方便对nums1进行遍历时的查找
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:st []res [-1]*len(nums2)for index,num in enumerate(nums2):# print(index,num)while st and nums2[st[-1]]num:j st.pop()res[j] numst.append(index)# 使用zip通过两个可迭代的对象构造字典myhash dict(zip(nums2,res))ans []for n1 in nums1:ans.append(myhash[n1])return ansclass Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:myhash {}st []res []for index, n in enumerate(nums2):while st and nums2[st[-1]] n:myhash[nums2[st.pop()]] nst.append(index)for n1 in nums1:res.append(myhash.get(n1, -1))return res503、下一个更大元素II 出现这种需要循环才能判断的情况可以采用求余数的方法来多遍历一次。
类似的思路还有打家劫舍II中头尾不能同时偷的情况就可以采用将数组列表进行拆分0-n-1和1-n的情况
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:# 如何解决循环的问题# 循环也就最多循环一轮到自己本身# 用求余来表示res [-1] * len(nums)st []for index, n in enumerate(nums * 2):while st and nums[st[-1]] n:res[st.pop()] nst.append(index % len(nums))return res42、接雨水 在做本题之前需要明确计算的方法是按照行进行计算还是按照列进行计算这两个计算方法的不同会导致不同的做法。
按照行去计算的做法如下所示逐行进行累加 按照列去计算的做法如下所示逐列进行累加 按照列去计算的时候可以假设每一列的宽度为1只需要逐列去进行累加即可得到最终结果这个思路也衍生了下面的暴力算法 暴力算法【逐列累加】
暴力算法的思路是一列一列的去记录能够装的雨水是多少最终累加起来。
记录每个节点左边和右边的最大高度然后用两个最大高度中的最小值减去当前高度然后乘以宽度1将这个值累加到res中。
s (min(lHeight,rHeight)-height[i]) * 1当遍历到第一个柱子和最后一个柱子的时候不需要计算面积。对于其余的柱子需要寻找其左边和右边的最高的柱子然后取两者中的最小值用最小值的高度减去height[i]得到差值就是可以装的雨水的高度然后用这个高度再乘以宽度1就是能装的雨水的体积。最后一直累加这个和得到能装的最多的雨水。
lHeight height[i]
rHeight height[i]
for j in range(i 1, len(height)):rHeight max(rHeight, height[j])
for j in range(i - 1, -1, -1):lHeight max(lHeight, height[j])
res min(lHeight, rHeight) - height[i]很不幸代码超时了。 class Solution:def trap(self, height: List[int]) - int:# 暴力算法从前往后进行遍历记录当前位置左右的最高点res 0for i in range(1, len(height) - 1):lHeight height[i]rHeight height[i]for j in range(i 1, len(height)):rHeight max(rHeight, height[j])for j in range(i - 1, -1, -1):lHeight max(lHeight, height[j])res min(lHeight, rHeight) - height[i]# print(i,lHeight,rHeight res min(lHeight, rHeight) - height[i]return res双指针【逐列累加】
在暴力算法中每轮循环都需要重复去寻找当前位置左右更高的高度可以采用双指针的方法进行优化
注意双指针方法和暴力算法本质上都是逐列进行累加的。
通过两个单独的for循环得到lHeight和rHeight数组分别表示每个柱子左右两侧的最高的高度是多少然后在通过一次循环从1遍历到n-2位置的柱子然后累加最终能够装的雨水的体积。
这里需要注意在循环的时候需要进行赋初始值例如找左侧最大值的时候下标为0的地方赋初值height[0]不需要进行比较然后从下标1到n-1进行遍历。具体的可以参考下图 rHeight [0] * n
lHeight [0] * n
# 计算每个柱子左侧的最高高度
lHeight[0] height[0]
for i in range(1, n - 1):lHeight[i] max(lHeight[i - 1], height[i])
# print(lHeight)
rHeight[n - 1] height[n - 1]
for i in range(n - 2, -1, -1):rHeight[i] max(rHeight[i 1], height[i])找到左边和右边的最高值计算一列可以装的水有多少
记录每个柱子左边的最高高度和右边的最高高度然后高度就是min(左边最高高度右边最高高度)-height[i]宽度就是1
class Solution:def trap(self, height: List[int]) - int:# 双指针n len(height)if n2:return 0res 0lheight [0]*nrheight [0]*nlheight[0] height[0] # 进行初始化for i in range(1,n-1):lheight[i] max(lheight[i-1],height[i])rheight[n-1] height[n-1] # 进行初始化for i in range(n-2,-1,-1):rheight[i] max(rheight[i1],height[i])# print(lheight,rheight)for i in range(1,n-1):res min(lheight[i],rheight[i])-height[i]return res单调栈【逐行累加】
单调栈的核心思路是逐行进行累加
单调栈的思路就是如果栈为空则先第一个柱子入栈紧接着如果第二个柱子的高度低于栈中柱子的高度则继续入栈。也就是说此时栈中的元素从栈顶到栈底是从小到大的顺序。只有从小到大的顺序才能够再下一次遇到一个比栈顶元素高的柱子的时候形成一个凹槽然后计算能够装的雨水的体积是多少。
如果遇到相同高度的柱子这时我们需要保存的是最新的下标这里需要将原来的栈顶元素pop弹出然后将当前的下标i放到栈顶中。
如果出现一种情况是当前遍历的高度高于栈顶元素的高度那么弹出栈顶元素此时如果栈不为空则开始计算雨水。此时的栈顶的元素的高度就是凹槽的高度当前遍历的就是凹槽右边的高度然后栈顶的下一个元素就是左侧的较高的柱子。right-left-1就是宽度乘以min(left,right)-height[i]就是最终的面积。 这里详细解释一下面积计算的方法长×高 长 当前遍历的下标位置 - 左侧最高高度下标位置 - 1 高 min(左侧最高高度右侧最高高度) - 当前柱子高度具体体现为当前遍历元素为右侧最高高度栈顶的元素为凹槽处的高度栈顶的下一个元素为左侧最高高度。 例如下面这张图中当我遍历到位置5的时候其计算其长度应该5-1-13然后高度为min(3,2)-1 1所以面积就是3*13。可以看出来这一行的面积确实就是3符合我们的计算公式。 具体的分为下面三种情况
当前遍历的柱子的高度低于栈顶元素的高度则继续入栈当前遍历的柱子的高度等于栈顶元素的高度则将栈顶元素弹出更新最新柱子高度将新的柱子下标入栈当前遍历的柱子的高度大于栈顶元素的高度此时形成凹槽了就计算雨水的面积了。
class Solution:def trap(self, height: List[int]) - int:st []res 0for index, h in enumerate(height):while st and height[st[-1]] h:j st.pop()if st:res (index - st[-1] - 1) * (min(h, height[st[-1]]) - height[j])if st and height[st[-1]] h:st.pop()st.append(index)return res84、柱状图中最大的矩形 暴力解法
在暴力解法中从每个下标i位置出发找到左右两侧比其高的位置但是一旦出现比其低的位置直接break记录下左右下边left和right然后用right-left-1作为底面宽度height[i]作为高度得到最终的面积。将这个面积与sum_进行比较取两者中的最大值。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:# 暴力解法sum_ 0for i in range(len(heights)):left, right i, iwhile left 0:if heights[left] heights[i]:breakleft - 1while right len(heights):if heights[right] heights[i]:breakright 1sum_ max(sum_, (right - left - 1) * heights[i])return sum_双指针法
记录每个柱子左边的第一个小于该柱子的下标而不是记录左边第一个小于该柱子的高度
双指针的难点就在于如何去寻找当前位置i的左右两侧第一个比其低的柱子的下标
此部分的代码如下
这里在寻找的时候需要进行初始化不然的话while循环可能死循环。
注意这里如果minLeftIndex数组中元素值为-1或者minRightIndex数组中元素值为len(heights)表示该柱子左边或者右边没有比其更矮的柱子此时就以这个柱子的高度乘以宽度即可。
minLeftIndex[0] -1
for i in range(1,n):t i-1while t0 and heights[t]heights[i]:t minLeftIndex[t] # 左移minLeftIndex[i] t
# print(minLeftIndex)
minRightIndex[n-1] n
for i in range(n-2,-1,-1):t i1while tn-1 and heights[t]heights[i]:t minRightIndex[t]minRightIndex[i] t完整代码如下
class Solution:def largestRectangleArea(self, heights: List[int]) - int:# 双指针法n len(heights)minLeftIndex [0]*nminRightIndex [0]*n# 寻找左边的小于他的下标minLeftIndex[0] -1for i in range(1,n):t i-1while t0 and heights[t]heights[i]:t minLeftIndex[t] # 左移minLeftIndex[i] t# print(minLeftIndex)minRightIndex[n-1] nfor i in range(n-2,-1,-1):t i1while tn-1 and heights[t]heights[i]:t minRightIndex[t]minRightIndex[i] t# print(minRightIndex)res 0for i in range(n):res max(res,(minRightIndex[i]-minLeftIndex[i]-1)*heights[i])return res单调栈法
在接雨水一题中我们想要实现的效果是寻找到一个凹槽即找到一个柱子左右两侧高于该柱子的柱子然后逐行求面积。而本题所需要实现的效果是寻找一个柱子左右两侧低于该柱子的柱子。
单调栈中的顺序从栈顶到栈底应该是从大到小的。这样就方便找到每个节点的左边或者右边低于其高度的柱子。当遍历到下一个柱子的高度小于栈顶元素的时候就可以进行弹出了。在弹出的时候计算高度即可得到最终的答案。
本质上这道题跟接雨水差不多都可以分成如下三种情况
情况1当前遍历的元素height[i]大于栈顶元素height[st[-1]]此时需要入栈情况2当前遍历的元素height[i]等于栈顶元素height[st[-1]]此时需要将栈顶元素弹出然后更新最新的柱子高度对应的下标情况3当前遍历的元素height[i]小于栈顶元素height[st[-1]]此时可以进行面积的计算了
计算面积的时候高度是中间的高度
本题还有一个需要注意的细节就是需要再heights数组的开头和结尾加上一个0元素这是因为
如果数组原本就是一个升序的如[1,2,3,4,5]进入栈中变成[5,4,3,2,1]就不会走情况3进行面积的计算所以需要在最后加上0强制让其进行结果的计算
如果数组原本就是一个降序的如[5,4,3,2,1]进入栈中就会导致无法计算面积因为目前栈中还是空的。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:# 单调栈heights.insert(0,0)heights.append(0)stack [0]res 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 stack.pop()if stack:left_index stack[-1]right_index iwidth right_index - left_index - 1height heights[mid]res max(res,width*height)stack.append(i)return res优化版本
class Solution:def largestRectangleArea(self, heights: List[int]) - int:heights.append(0)heights.insert(0,0)st []res 0for index,h in enumerate(heights):while st and hheights[st[-1]]:# 开始进行计算面积mid st.pop()if st:left st[-1]right indexres max(res,heights[mid]*(right-left-1))if st and heights[st[-1]]h:st.pop()st.append(index)return resclass Solution:def largestRectangleArea(self, heights: List[int]) - int:heights.insert(0, 0)heights.append(0)# print(heights)st []res 0for index in range(len(heights)):while st and heights[st[-1]] heights[index]:# 计算面积j st.pop()if st:res max(res, (index - st[-1] - 1) * heights[j])if st and heights[st[-1]] heights[index]:st.pop()st.append(index)return res1944、队列中可以看到的人数 题目解析本题需要计算一个人能看到其右边的人的人数如果两个人中间还有其他人并且前一个人的高度高于后一个人的高度则后面这个人是无法被看见的。
单调栈的本质及时去掉没有用的数据。
本题单调栈中存放的是人的高度并且单调栈中的元素从栈顶到栈底是一个递增的顺序。
本题不是采取的从前往后进行遍历的方式这样的遍历方式无法避免掉被阻挡掉的矮个子因此需要从后往前进行遍历如果当前人的高度比栈中的人的高度高则栈中元素弹出并且当前人可以看到的人数加1同时如果栈不为空的情况当前的人还可以看到一个人需要加1然后将当前人的高度入栈。
class Solution:def canSeePersonsCount(self, heights: List[int]) - List[int]:n len(heights)ans [0]*nst []for i in range(n-1,-1,-1):while st and st[-1]heights[i]:st.pop()ans[i]1if st:ans[i]1st.append(heights[i])return ans
