知名手机网站,wordpress windows 伪静态,免费制作微信小程序软件,电商网站流程题目
双指针
思路1
使用参数存储从左往右#xff08;从右往左同理#xff09;遍历时的最高的柱子#xff0c;
然后移动左右的指针#xff0c;每次移动左右指针中偏向小的#xff0c;
如果当前指针指的柱子小于最高的柱子#xff0c;就会存在接到水。
思路2
把水看作柱子从右往左同理遍历时的最高的柱子
然后移动左右的指针每次移动左右指针中偏向小的
如果当前指针指的柱子小于最高的柱子就会存在接到水。
思路2
把水看作柱子那么整个柱子都会变成凸的样子不会出现凹的情况如果有凹会被水填满
那么我们的参数l_maxr_max就是在记录凸的地方和height里的凹的数据进行比较记录雨水。
class Solution(object):def trap(self, height): len_h len(height)l, r 0, len_h - 1l_max, r_max 0, 0ans 0while l r:l_max max(l_max, height[l])r_max max(r_max, height[r])if height[l] height[r]:ans l_max - height[l]l 1else:ans r_max - height[r]r - 1return ans
动态规划
思路分别记录从左到右/从右到左的的最高柱子思路和双指针一样class Solution:def trap(self, height: List[int]) - int:if not height:return 0n len(height)leftMax [height[0]] [0] * (n - 1)for i in range(1, n):leftMax[i] max(leftMax[i - 1], height[i])rightMax [0] * (n - 1) [height[n - 1]]for i in range(n - 2, -1, -1):rightMax[i] max(rightMax[i 1], height[i])ans sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))return ans
前后缀分解
思路和双指针思路相似记录两边的最高柱
class Solution(object):def trap(self, height)::type height: List[int]:rtype: intn len(height)# pre_max [0] * n# pre_max[0] height[0]pre_max height.copy()for i in range(1, n):pre_max[i] max(pre_max[i-1], height[i])suf_max [0] * n # suf_max[i] 表示从 height[i] 到 height[n-1] 的最大值suf_max[-1] height[-1]for i in range(n - 2, -1, -1):suf_max[i] max(suf_max[i 1], height[i])ans 0for h, pre, suf in zip(height, pre_max, suf_max):ans min(pre, suf) - h #累计每个水桶能接多少水return ans 栈
思路
使用栈按单调递减记录左边柱子的情况当识别到高于目前栈顶的元素的时候不断弹出栈顶的元素作为坑底将栈前一个元素作为左边界当前元素h作为右边界横着计算水坑。while循环就是不断地计算横着的水坑直到识别到左边没有合适的边界无法形成水坑/左边的边界大于当前元素。最后将目前的柱子推入栈。
注意 while 中加了等号这可以让栈中没有重复元素从而在有很多重复元素的情况下使用更少的空间。
class Solution(object):def trap(self, height)::type height: List[int]:rtype: intans 0st []for i, h in enumerate(height):# 当栈不为空且当前高度大于栈顶索引对应的高度时while st and height[st[-1]] h: bottom_h height[st.pop()] # 弹出栈顶元素这个位置将作为水坑底部if not st: # 如果栈空了说明左边没有更高的边界无法形成水坑break left st[-1] # 此时栈顶元素就是左边界dh min(height[left], h) - bottom_h # 计算水坑的高度左右边界中较低的那个减去底部高度ans dh * (i - left - 1)# 计算水坑的宽度当前位置到左边界的距离减1st.append(i) # 把当前位置加入栈保持栈的单调递减特性return ans
