网站样版风格排版,2022年适合小学生的新闻,网站没有后台怎么更新文章,网站是做排行榜一、栈
1、每日温度
使用单调递减栈来解决。主要思路是遍历temperatures数组#xff0c;利用栈来存储还没有找到比当前温度高的天数的索引。当遇到比栈顶索引所对应温度更高的温度时#xff0c;就可以确定当前这一天的温度比之前那一天高。索引的差值就是等待的天数。
求一…一、栈
1、每日温度
使用单调递减栈来解决。主要思路是遍历temperatures数组利用栈来存储还没有找到比当前温度高的天数的索引。当遇到比栈顶索引所对应温度更高的温度时就可以确定当前这一天的温度比之前那一天高。索引的差值就是等待的天数。
求一个元素右边或者左边第一个比它大/小的元素可以用到单调栈。
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:nlen(temperatures)stk[]ans[0]*nfor i in range(n):tmptemperatures[i]while stk and tmptemperatures[stk[-1]]:pre_posstk.pop()ans[pre_pos]i-pre_posstk.append(i)return ans
2、柱状图中最大的矩形
代码随想录题解http://【单调栈又一次经典来袭 LeetCode84.柱状图中最大的矩形】https://www.bilibili.com/video/BV1Ns4y1o7uB?vd_sourceb93b9c2a7846dd3e8bd33feb227c4ac5通过使用单调递增栈来解决这个问题。当遇到一个比栈顶元素低的高度时说明以栈顶高度为矩形的柱子已经结束它无法再延伸更大的宽度因此可以计算这个柱子形成的最大矩形面积。
单调栈的核心是维护一个递增序列。具体思路是
如果当前柱子的高度大于栈顶柱子的高度则将当前柱子的索引压入栈。如果当前柱子的高度小于栈顶柱子的高度说明栈顶柱子的矩形已经找到了右边界因此我们可以计算以该柱子为高度的最大矩形面积。
我们要找到直方图中能够形成的最大矩形面积。这个问题的关键在于如何快速计算每个柱子作为矩形高度时能够向左和向右延伸的宽度。为了高效地解决这个问题我们使用单调栈它帮助我们在每次遇到更矮的柱子时回溯并计算以之前柱子为高度的最大矩形面积。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:heights[0]heights[0]res0stk[0]for i in range(1,len(heights)):if heights[i]heights[stk[-1]]:stk.append(i)elif heights[i]heights[stk[-1]]:stk.pop()stk.append(i)else:while stk and heights[stk[-1]]heights[i]:mid_height_posstk.pop()mid_heightheights[mid_height_pos]left_edgestk[-1]right_edgeiresmax(res,(right_edge-left_edge-1)*mid_height)stk.append(i)return res 二、堆
1、数组中的第k个最大元素
①快速排序思想
题目要求是找出数组中第k个最大元素因此可以通过快速排序不断缩小寻找区间来定位第k个最大的元素。题目要求找的是数组中第k个最大的元素因此排序后的元素是从大到小逆序排列的左右指针移动的判断条件不要写错。
与快速排序不同的是不需要完全排序整个数组只需要处理包含第 k 大元素的那一部分。因此每交换过一轮元素以后都要判定第k大的元素在左边部分每次的起始left到j还是右部分j1到right)。
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:def quicksort(nums,left,right,k):if leftright:return nums[left]mid(leftright)//2pivotnums[mid]i,jleft-1,right1while ij:while True:i1if nums[i]pivot:breakwhile True:j-1if nums[j]pivot:breakif ij:nums[i],nums[j]nums[j],nums[i]if j-left1k:return quicksort(nums,left,j,k)else:return quicksort(nums,j1,right,k-(j-left1))return quicksort(nums,0,len(nums)-1,k)
②堆
维护一个大小为 k 的小根堆。每次当堆的大小超过 k 时弹出堆顶元素因为堆顶元素是堆中最小的这样可以确保堆中始终保留了 k 个最大的元素。最后堆顶的元素就是第 k 大的元素。
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:min_heap[]for num in nums:heapq.heappush(min_heap,num)if len(min_heap)k:heapq.heappop(min_heap)return min_heap[0]
2、前K个高频元素
与1-数组中的第k个最大元素中堆处理方法处理思想相同。
首先调用Counter方法获取每个元素与其出现次数再构建一个小根堆来存放出现次数数组元素堆顶是出现次数最少的数组元素。每当堆的大小超过k就将堆顶元素弹出这样最后留在堆中的一定是出现次数最多的那K个数组元素。
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:counterCounter(nums)heap[]for num,count in counter.items():heapq.heappush(heap,(count,num))if len(heap)k:heapq.heappop(heap)list_k[heap[i][1] for i in range(k)]return list_k
3、数据流的中位数
整体思路
使用一个最大堆通过存负值模拟来保存数据流中较小的一半元素。使用一个最小堆来保存数据流中较大的一半元素。保持最大堆的大小总是等于最小堆的大小或者比最小堆大一个元素这样中位数可以轻松获取 如果两个堆的大小相同则中位数是两个堆顶元素的平均值。如果最大堆比最小堆大一个元素则中位数是最大堆的顶部元素。
详细步骤 添加元素 首先添加到最大堆: 元素以其负值形式添加到最大堆中。调整元素到最小堆: 如果添加后最大堆的堆顶元素负值的最小值即绝对值最大大于最小堆的堆顶元素则将最大堆的顶部元素弹出转换为正值并加入到最小堆中。这样做是为了保证最小堆中的所有元素始终大于最大堆中的所有元素。平衡两个堆的大小: 如果最大堆的大小比最小堆大超过1个元素从最大堆中移除顶部元素最大值转换为正值后加入到最小堆中。如果最小堆比最大堆大虽然按照逻辑不应该发生但为了保证健壮性也可以检查和处理则将最小堆的顶部元素弹出并加入到最大堆中。 计算中位数: 如果最大堆的元素数量比最小堆多中位数是最大堆的堆顶元素转换为正值。如果最大堆和最小堆的大小相同中位数是两个堆顶元素值的平均数。
class MedianFinder:def __init__(self):self.min_heap[]self.max_heap[]def addNum(self, num: int) - None:heapq.heappush(self.max_heap,-num)if self.max_heap and self.min_heap and -self.max_heap[0]self.min_heap[0]:heapq.heappush(self.min_heap,-heapq.heappop(self.max_heap))if len(self.max_heap)len(self.min_heap)1:heapq.heappush(self.min_heap,-heapq.heappop(self.max_heap))if len(self.min_heap)len(self.max_heap):heapq.heappush(self.max_heap,-heapq.heappop(self.min_heap))def findMedian(self) - float:if len(self.max_heap)len(self.min_heap):return (-self.max_heap[0]self.min_heap[0])/2.0else:return -self.max_heap[0]# Your MedianFinder object will be instantiated and called as such:
# obj MedianFinder()
# obj.addNum(num)
# param_2 obj.findMedian() 三、贪心算法
1、买卖股票的最佳时机
①题意限制
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。
并且卖出股票的价格需要比买入股票的价格高。
②解题思路
维护两个变量max_profit和min_price分别记录当前最大利润和当前最小价格。
最大利润一定是由较高的价格减去它之前最低的价格获得的。
遍历每个prices数组中的每个price根据price更新max_profit和min_price
max_profitmax(max_profit,price-min_price)min_pricemin(price,min_price)
class Solution:def maxProfit(self, prices: List[int]) - int:max_profit0min_pricefloat(inf)for price in prices:max_profitmax(price-min_price,max_profit)min_pricemin(min_price,price)return max_profit
2、跳跃游戏
①题意解读
给你一个非负整数数组 nums 你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
题目忽略的部分
在当前跳跃游戏和下一个跳跃游戏II中在 nums[i] 处你可以跳转到任意 nums[i j] 处其中0 j nums[i] 。
举个例子在【2,3,1,4,2】中从起点nums[0]2开始跳跃当前最远可达索引位置是nums[0]02nums[0]可以选择跳跃到3也可以选择跳到当前最远1。
②思路解析
能否到达最后一个下标取决于从数组第一个下标开始跳跃能到达的最远位置。
因此我们可以维护一个记录当前可达最远位置的变量right遍历数组中每一个元素若当前遍历到的数组索引 i 大于right就说明当前位置 i 是跳跃到达不了的。
若right的值大于等于数组中最后一个下标索引则说明能够到达终点。
class Solution:def canJump(self, nums: List[int]) - bool:nlen(nums)right0for i in range(n):if iright:rightmax(right,nums[i]i)if rightn-1:return Truereturn False
3、跳跃游戏II
①题意说明
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n
返回到达 nums[n - 1] 的最小跳跃次数。
②思路解析
维护两个变量right和end分别记录能够到达的最远位置和目前所在跳跃区间的终点。
right和上一个跳跃游戏表示的意思是一样的。
end是目前所在跳跃区间的终点。举个例子【23156】紫色标识的部分便是从起点nums[0]开始的跳跃区间end此时指向索引2。遍历到end的时候就不得不做一次跳跃了而跳跃的根据取决于right确保每次跳跃都能到达更远的位置。
利用【23156】辅助说明i0时right2i1时right4iend2时right3在这个跳跃区间内更新了right的情况。到达end2时需要从起点执行一次跳跃操作可以跳到索引位置1nums[1]3也可以跳到索引位置2nums[2]1而根据right的信息我们可以知道这一跳跳到索引位置1的收益最大因此当前这一跳跳到索引位置1跳跃区间发生变化区间终点end的值更新为当前right。
class Solution:def jump(self, nums: List[int]) - int:if len(nums)1:return 0nlen(nums)jump0right0end0for i in range(n):rightmax(right,inums[i])if iend:jump1endrightif endn-1:breakreturn jump
4、划分字母区间
首先数组last来记录每个字母最后一次出现的位置。
维护两个变量start和end分别记录当前区间开始的位置和当前区间结束的位置。
遍历字符串比较当前字母的最后一次出现位置与当前子区间终点end的大小若前者更大则更新end。若当前索引与end相等表示该子区间遍历结束另起起点划分区间。
class Solution:def partitionLabels(self, s: str) - List[int]:last[0]*26for i,ch in enumerate(s):posord(ch)-ord(a)last[pos]istart0end0partition[]for i,ch in enumerate(s):posord(ch)-ord(a)endmax(end,last[pos])if iend:partition.append(end-start1)startend1return partition
