HOT 100(七)栈、堆、贪心算法

一、栈

1、每日温度

使用单调递减栈来解决。主要思路是遍历temperatures数组,利用栈来存储还没有找到比当前温度高的天数的索引。当遇到比栈顶索引所对应温度更高的温度时,就可以确定当前这一天的温度比之前那一天高。索引的差值就是等待的天数

求一个元素右边或者左边第一个比它大/小的元素可以用到单调栈。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n=len(temperatures)
        stk=[]
        ans=[0]*n
        for i in range(n):
            tmp=temperatures[i]
            while stk and tmp>temperatures[stk[-1]]:
                pre_pos=stk.pop()
                ans[pre_pos]=i-pre_pos
            stk.append(i)
        return ans

2、柱状图中最大的矩形 

代码随想录题解icon-default.png?t=O83Ahttp://【单调栈,又一次经典来袭! LeetCode:84.柱状图中最大的矩形】https://www.bilibili.com/video/BV1Ns4y1o7uB?vd_source=b93b9c2a7846dd3e8bd33feb227c4ac5通过使用单调递增栈来解决这个问题。当遇到一个比栈顶元素低的高度时,说明以栈顶高度为矩形的柱子已经结束,它无法再延伸更大的宽度,因此可以计算这个柱子形成的最大矩形面积。

单调栈的核心是维护一个递增序列。具体思路是:

  • 如果当前柱子的高度大于栈顶柱子的高度,则将当前柱子的索引压入栈。
  • 如果当前柱子的高度小于栈顶柱子的高度,说明栈顶柱子的矩形已经找到了右边界,因此我们可以计算以该柱子为高度的最大矩形面积。

我们要找到直方图中能够形成的最大矩形面积。这个问题的关键在于如何快速计算每个柱子作为矩形高度时,能够向左和向右延伸的宽度。为了高效地解决这个问题,我们使用单调栈,它帮助我们在每次遇到更矮的柱子时回溯并计算以之前柱子为高度的最大矩形面积。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights=[0]+heights+[0]
        res=0
        stk=[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_pos=stk.pop()
                    mid_height=heights[mid_height_pos]
                    left_edge=stk[-1]
                    right_edge=i
                    res=max(res,(right_edge-left_edge-1)*mid_height)
                stk.append(i)
        return res

二、堆

1、数组中的第k个最大元素

①快速排序思想

题目要求是找出数组中第k个最大元素,因此可以通过快速排序不断缩小寻找区间来定位第k个最大的元素。(题目要求找的是数组中第k个最大的元素,因此排序后的元素是从大到小逆序排列的,左右指针移动的判断条件不要写错)。

与快速排序不同的是,不需要完全排序整个数组,只需要处理包含第 k 大元素的那一部分。因此每交换过一轮元素以后,都要判定第k大的元素在左边部分(每次的起始left到j)还是右部分(j+1到right)。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quicksort(nums,left,right,k):
            if left>=right:
                return nums[left]
            mid=(left+right)//2
            pivot=nums[mid]
            i,j=left-1,right+1
            while i<j:
                while True:
                    i+=1
                    if nums[i]<=pivot:
                        break
                while True:
                    j-=1
                    if nums[j]>=pivot:
                        break
                if i<j:
                    nums[i],nums[j]=nums[j],nums[i]
            if j-left+1>=k:
                return quicksort(nums,left,j,k)
            else:
                return quicksort(nums,j+1,right,k-(j-left+1))
        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]:
        counter=Counter(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.0
        else:
            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_profit=max(max_profit,price-min_price)
  • min_price=min(price,min_price)
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit=0
        min_price=float('inf')
        for price in prices:
            max_profit=max(price-min_price,max_profit)
            min_price=min(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]+0=2,nums[0]可以选择跳跃到3,也可以选择跳到当前最远1。

②思路解析

能否到达最后一个下标,取决于从数组第一个下标开始跳跃能到达的最远位置

因此我们可以维护一个记录当前可达最远位置的变量right,遍历数组中每一个元素,若当前遍历到的数组索引 i 大于right,就说明当前位置 i 是跳跃到达不了的。

若right的值大于等于数组中最后一个下标索引,则说明能够到达终点。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n=len(nums)
        right=0
        for i in range(n):
            if i<=right:
                right=max(right,nums[i]+i)
                if right>=n-1:
                    return True
        return 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是目前所在跳跃区间的终点。举个例子【231,5,6】紫色标识的部分便是从起点nums[0]开始的跳跃区间,end此时指向索引2。遍历到end的时候,就不得不做一次跳跃了,而跳跃的根据取决于right,确保每次跳跃都能到达更远的位置

利用【231,5,6】辅助说明:i=0时,right=2;i=1时,right=4;i=end=2时,right=3(在这个跳跃区间内更新了right的情况)。到达end=2时需要从起点执行一次跳跃操作,可以跳到索引位置1(nums[1]=3),也可以跳到索引位置2(nums[2]=1),而根据right的信息我们可以知道这一跳跳到索引位置1的收益最大,因此当前这一跳跳到索引位置1,跳跃区间发生变化,区间终点end的值更新为当前right。

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)<=1:
            return 0
        n=len(nums)
        jump=0
        right=0
        end=0
        for i in range(n):
            right=max(right,i+nums[i])
            if i==end:
                jump+=1
                end=right
                if end>=n-1:
                    break
        return jump

4、划分字母区间

首先,数组last来记录每个字母最后一次出现的位置。

维护两个变量start和end,分别记录当前区间开始的位置和当前区间结束的位置。

遍历字符串,比较当前字母的最后一次出现位置与当前子区间终点end的大小,若前者更大则更新end。若当前索引与end相等,表示该子区间遍历结束,另起起点划分区间。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last=[0]*26
        for i,ch in enumerate(s):
            pos=ord(ch)-ord('a')
            last[pos]=i
        start=0
        end=0
        partition=[]
        for i,ch in enumerate(s):
            pos=ord(ch)-ord('a')
            end=max(end,last[pos])
            if i==end:
                partition.append(end-start+1)
                start=end+1
        return partition

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/876058.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Golang数据流处理:掌握Reader和Writer接口的技巧

Golang数据流处理&#xff1a;掌握Reader和Writer接口的技巧 引言理解Reader和Writer接口Reader接口的定义和基本方法Writer接口的定义和基本方法 Reader接口的深入探讨Reader接口的实现示例使用io.Reader读取文件内容从网络连接中读取数据 常用Reader类型及其应用场景strings.…

相图的科学应用,陶瓷材料创新

陶瓷材料因其优异的物理和化学性能&#xff0c;在航空航天、电子、生物医学等多个领域展现出广阔的应用前景。陶瓷材料的性能很大程度上取决于其微观结构&#xff0c;包括晶粒大小、相组成和分布。相图作为描述陶瓷材料在不同条件下的相变行为和相平衡关系的图表反映了陶瓷材料…

10年Python程序员教你多平台采集10万+电商数据【附实例】

10万级电商数据采集需要注意什么&#xff1f; 在进行10万级电商数据采集时&#xff0c;有许多关键因素需要注意&#xff1a; 1. 采集平台覆盖&#xff1a;确保可以覆盖主流的电商平台&#xff0c;如淘宝、天猫、京东、拼多多等。 2. 数据字段覆盖&#xff1a;检查是否可以对平…

什么是VHDX文件?

VHDX文件是Docker环境中使用的一种虚拟硬盘文件格式&#xff0c;专门用于存储Docker容器 的镜像和数据。这种文件格式&#xff0c;VHDX&#xff0c;代表Virtual Hard Disk Extended&#xff0c;是一种用于虚拟化环境的硬盘文件格式&#xff0c;支持动态扩展、快照、加密等功能&…

python基础知识 (五)--容器、索引、切片、字符串的遍历、查找、修改元素

目录 容器 容器大总结 索引 切片 字符串的遍历 for循环语法&#xff1a; while循环语法&#xff1a; 查找元素 修改元素 例题 1.验证码 2.抽取大红包 3.a和b互换位置 容器 在Python中&#xff0c;常见容器有&#xff1a; &#xff08;1&#xff09;字符串&#x…

C++:类和对象全解

C&#xff1a;类和对象全解 一、类的定义和初始化&#xff08;一&#xff09;类的定义1、类的成员变量&#xff08;1&#xff09;成员变量&#xff08;2&#xff09;成员函数 2、实例化对象&#xff08;1&#xff09;采用普通构造函数&#xff08;2&#xff09;采用初始化列表 …

数据可视化与分析:数据时代的关键工具

一、引言 数据可视化与分析是大数据时代中最为重要的技术之一。随着数据量的不断增加&#xff0c;如何有效地理解、解释和利用数据&#xff0c;已经成为各行各业面临的关键挑战。数据可视化通过图表、图形和互动界面将数据以直观的方式呈现&#xff0c;帮助用户快速识别数据中…

SMA2:代码实现详解——Image Encoder篇(Hiera章)

SMA2:代码实现详解——Image Encoder篇&#xff08;Hiera&#xff09; 写在前面 大家在SMA2:代码实现详解——Image Encoder篇&#xff08;FpnNeck&#xff09;下的留言我已收到&#xff0c;感谢大家的支持&#xff0c;后面如果遇到比较难以讲清的部分可能会使用视频的形式。…

Python 课程9-資料庫操作

前言 在现代软件开发中&#xff0c;数据库是核心组件之一&#xff0c;它负责数据的存储、管理和检索。无论是简单的应用程序还是复杂的企业级系统&#xff0c;数据库操作都是必不可少的。本教程将深入讲解如何使用 Python 进行数据库操作&#xff0c;涵盖使用 sqlite3 进行本地…

OpenHarmony(鸿蒙南向开发)——轻量系统STM32F407芯片移植案例

往期知识点记录&#xff1a; 鸿蒙&#xff08;HarmonyOS&#xff09;应用层开发&#xff08;北向&#xff09;知识点汇总 鸿蒙&#xff08;OpenHarmony&#xff09;南向开发保姆级知识点汇总~ OpenHarmony&#xff08;鸿蒙南向开发&#xff09;——轻量和小型系统三方库移植指南…

Android SystemUI组件(06)导航栏创建分析虚拟按键

该系列文章总纲链接&#xff1a;专题分纲目录 Android SystemUI组件 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节持续迭代之前章节的思维导图&#xff0c;主要关注左侧SystemBars分析中导航栏部分即可。 1 导航栏创建之makeStatusBarView 通过上一篇文章的…

代理IP设置后IP不变?可能的原因及解决方法

在使用代理IP时&#xff0c;有时会遇到代理设置后IP地址却没有变化的情况。这种问题可能会让人感到困惑&#xff0c;但其实背后有多种原因。本文将详细探讨这些原因&#xff0c;并提供相应的解决方法&#xff0c;帮助你顺利解决问题。 可能的原因 代理IP设置后IP地址不变的原…

Spring的核心思想

目录 一、Spring要解决的问题 二、Spring的核心结构 三、核心思想 3.1.1 什么是IOC 3.1.2 IOC解决的问题&#xff1a;耦合 3.1.3 IOC和DI的区别 3.2.1 什么是AOP 3.2.2 AOP解决的问题&#xff1a;耦合 3.2.3 为什么叫做面向切面编程 一、Spring要解决的问题 问题1&am…

maya-vray渲染蒙版

要用一个叫vrayMulWrapper的材质球&#xff0c;把alpha Conterbution调到-1&#xff0c;勾选matte surface启用蒙版物体。

爬虫逆向学习(六):补环境过某数四代

声明&#xff1a;本篇文章内容是整理并分享在学习网上各位大佬的优秀知识后的实战与踩坑记录 引用博客&#xff1a; https://blog.csdn.net/shayuchaor/article/details/103629294 https://blog.csdn.net/qq_36291294/article/details/128600583 https://blog.csdn.net/weixin_…

时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测

时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测 目录 时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测&#xff…

巴西电商市场规模、前景及支付方式(pix、Boleto)

一、巴西电商市场分析 作为拉丁美洲最大经济体&#xff0c;巴西在拉丁美洲经济中占据领先地位&#xff0c;根据巴西地理与统计研究所(IBGE)的数据&#xff0c;2023年巴西GDP达到2.2万亿美元&#xff0c;跃居世界第九大经济体。数字化进程以及经济多元化推进正在推动该国中产阶…

TiDB 数据库核心原理与架构_Lesson 01 TiDB 数据库架构概述课程整理

作者&#xff1a; 尚雷5580 原文来源&#xff1a; https://tidb.net/blog/beeb9eaf 注&#xff1a;本文基于 TiDB 官网 董菲老师 《TiDB 数据库核心原理与架构&#xff08;101) 》系列教程之 《Lesson 01 TiDB 数据库架构概述》内容进行整理和补充。 课程链接&#xff1a;…

PowerBI 关于FILTERS函数和VALUES函数

本人是powerbi新手&#xff0c;最近在使用Filters()函数和Values()函数时&#xff0c;有点不太明白它们之间的区别&#xff0c;u有时它们得到的结果是一样的&#xff0c;有时却不一样。 官方文档里&#xff0c;Filters()是表示返回直接作为筛选器应用到 columnName 的值 FILT…

凸优化学习(1)——什么是凸优化、凸集、凸函数

&#x1f345; 写在前面 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;这里是hyk写算法了吗&#xff0c;一枚致力于学习算法和人工智能领域的小菜鸟。 &#x1f50e;个人主页&#xff1a;主页链接&#xff08;欢迎各位大佬光临指导&#xff09; ⭐️近…