当前位置： 首页 > news >正文

LeetCodeHot100_0x09

news 2025/5/29 8:48:43

LeetCodeHot100_0x09

70. 最小栈·数据结构实现

求解思路： 一开始想着只用一个最小栈结构不就实现了，结果测试的时候发现，在pop元素后，它的最小值有可能不受影响，但是只用一个最小栈的话，最小值一定是作为栈顶元素最先被弹出了。而且题目要求弹出的元素是指按顺序插入的元素。因此原数据的插入顺序也需要用一个栈保存。也就是说，这题用两个Deque结构分别存储所有元素和维护当前元素存入时最小值的栈。

另外我看到评论区有老哥分享字节一面的进阶要求——不使用额外空间完成。

class MinStack {public Deque<Integer> stack;    // 保存所有元素public Deque<Integer> minStack; // 保存最小值的顺序// 初始化函数public MinStack() {stack = new LinkedList<Integer>();minStack = new LinkedList<Integer>();}// 推入堆栈public void push(int val) {// 普通栈直接插入stack.push(val);// 最小栈考虑插入if(minStack.isEmpty()) {minStack.push(val);}else {int topNum = minStack.peek();if(val < topNum) {minStack.push(val);}else {// 确保元素个数与普通栈相等，并可以很好反映每个元素插入时的当前最小值情况minStack.push(minStack.peek()); }}}// 删除栈顶元素public void pop() {// push保证了，所以两个一起删除就行stack.pop();minStack.pop();}// 获取栈顶元素public int top() {// 这个获取的是普通栈的栈顶return stack.peek();}// 常数时间（栈顶）public int getMin() {// 这个获取的是最小栈的栈顶return minStack.peek();}
}

71. 字符串解码

求解思路： 同样使用栈进行处理，这题的难点更多在于字符串的操作，主要需要判断四类东西：

  • 遇到数字（注意可能有多位）：
  • 遇到左括号：入队
  • 遇到右括号：出队
  • 遇到字符：加入到当前需要处理的字符串中
class Solution {public String decodeString(String s) {Deque<Integer> numStack = new ArrayDeque<>();       // 存储处理的次数Deque<StringBuilder> strStack = new LinkedList<>(); // 存储每一轮需要处理字符串StringBuilder res = new StringBuilder();  // 存储答案int num = 0; // 处理次数// 转成字符数组处理for(char c : s.toCharArray()) { //1. 判断是否为十进制数字if(Character.isDigit(c)) { // 整数的取值范围1--300，所以需要进行 num * 10num = num * 10 + (c - '0');  }//2. 判断碰到左括号else if(c == '[') {// 把本轮操作次数入栈numStack.push(num);  strStack.push(res);res = new StringBuilder();num = 0;   }//3. 判断碰到右括号，就需要将本轮的字符串和需要处理的次数取出来进行处理else if(c == ']') { // 保存原字符串StringBuilder currStr = res;// 取出本轮字符串res = strStack.pop();// 取出本轮处理次数int cnt = numStack.pop();for(int i=0;i<cnt;i++) {// 累加到答案中res.append(currStr);}}//4. 如果不是特殊符号，而是字符，那就加入到本轮字符串中else {res.append(c);}}return res.toString();}
}

72. 每日温度

求解思路： 暴力法找思路、优化暴力算法得到的逆向跳跃法可以解决问题。
【暴力大王】看看暴力能怎么优化

class Solution {public int[] dailyTemperatures(int[] temperatures) {// answer[i] 表示对于第i天，后面几天会出现更高温度// 先试试暴力解法int n = temperatures.length;int [] ans = new int[n];for(int i=0;i<n;i++) {int j;for(j=i+1;j<n;j++) {if(temperatures[j] > temperatures[i]) {ans[i] = j-i;break;}}if(j == n)ans[i] = 0;}return ans;}
}

【暴力优化——逆向跳跃法】将遍历顺序变成逆向的，这样可以优先处理出后面可复用的ans数组。

  • 定义j从距离i最近的位置开始探测
  • 如果当前探测位置j 存在 t[j] > t[i] ，探测结束直接更新 ans[i] = j-i;
  • 如果当前探测位置j 的ans = 0，表明后面没有比t[j]更大的了,又由于当前t[j] <= t[i],所以 ans[i] = 0
  • 如果当前探测位置j的ans != 0，为了提高探测效率，可以直接越过那些小于t[j]的位置，直接来到j + ans[j]的位置进行继续探测
class Solution {public int[] dailyTemperatures(int[] temperatures) {// 暴力优化——逆序跳跃法int n = temperatures.length;int[] ans = new int[n];// 因为是找后面有没有更大的，所以用倒过来处理的方法for(int i=n-2;i>=0;i--) {  // 从最接近i的位置开始探测 int j = i + 1;while(true) {//1.如果探测到当前位置大于i，保存答案 if(temperatures[j] > temperatures[i]) {ans[i] = j - i;break;}//2. 如果探测到当前位置ans数组为0，//   说明比t[j]大的不存在，并且由于t[i] > t[j],所以ans[i]也为0else if(ans[j] == 0) {ans[i] = 0;break;}//3. 走到这说明t[i] >= t[j] && ans[j] != 0// 也就是说，在j往后ans[j]的位置上 首次存在一个大于t[j]的值// 由于当前t[j] 小于 t[i], 只有大于t[j]的才有可能大于t[i]// 所以j 可以直接跳跃到 j + ans[j] 的位置上else {j += ans[j];    // 直接跳到比res[j]大的位置继续探测}}}return ans;}
}

73. 柱状图中最大的矩形（不会）

求解思路： 借着官解的图来看，我们首先要确定这道题它计算机是如何触发面积计算的。

  • 当我们遍历过程中，第一轮遍历到2，将它作为矩形高度的话，我们继续往后遍历，直到遍历到1，发现此时小于高度2了，那就触发当前面积计算，高度h = 2，宽度w = 右边界 - 左边界 = 2 - 0 = 2。
  • 再来，如果以5作为矩形高度呢?向右遍历到6，比5大，继续遍历；遍历到2，比5小，开始触发面积计算。
  • 再来，如果以6作为矩形高度呢?注意我们不仅仅要考虑后面未遍历的高度，也要留意前面已经遍历了的高度。以6作为矩形高度，向右遍历到2，触发面积计算，此时左边界是元素5的下标，右边界是元素2的下标

总结：

  • 计算机如何计算每个高度的面积呢？通过维护左右边界，左边出现第一个小于它的，右边出现第一个小于它的，这两个值的差作为该矩形的有效宽度，而有效高度就是当前高度。
  • 如何触发计算呢? 以当前高度所在下标开始向后遍历，找到第一个小于它的触发面积计算？
  • 如何快速保存上一个边界值的有效高度呢？可以通过栈来维护单调性
    在这里插入图片描述
    【哨兵单调栈】之所以加两个哨兵，前哨兵是为了避免空栈，后哨兵强制触发剩余元素的面积更新。
class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;// 在原数组首尾各添加一个0作为哨兵// 首哨兵：arr[0] = 0; 避免空栈检查// 尾哨兵：arr[n+1] = 0；强制剩余元素出栈计算面积int[] arr = new int[n + 2]; System.arraycopy(heights,0,arr,1,n); // 从heights[0] 开始依次拷贝到arr，拷贝n个元素// 栈的作用：存储柱子的下标，确保栈内对应高度是单调递增的Deque<Integer> stack = new LinkedList<>();stack.push(0);      // 左哨兵int maxArea = 0;    // 记录最大面积for(int i=1;i<arr.length;i++) {// 维护单调递增栈// 如果当前柱子高度小于栈顶对应高度时，触发面积计算while(arr[i] < arr[stack.peek()]) {int h = arr[stack.pop()];       // 获取当前栈顶的有效长度// 弹出完栈顶高度后，当前的stack.peek()是左边界下标// 当前 i 是右边界下标int width = i - stack.peek()-1; // 计算有效宽度maxArea = Math.max(maxArea, h * width);}// 压入当前下标，继续维护高度递增特性stack.push(i);}return maxArea;}
}

74. 数组中第k个最大元素

求解思路： 考察数据结构的选型，要求第k个大的数，可以用大小为k的最小堆来解决。遍历元素一遍，最后堆顶就是第k大的数。

class Solution {public int findKthLargest(int[] nums, int k) {// 利用大小为k的小堆解决，遍历完之后堆顶就是第k大的元素PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);for(int i=0;i<k;i++) {minQueue.offer(nums[i]);}for(int i=k;i<nums.length;i++) {if(nums[i] > minQueue.peek()) { // 大于当前最小，最小弹出，他加入minQueue.poll();minQueue.offer(nums[i]);}}return minQueue.peek();}
}

75. 前K个高频元素

求解思路： 前k个高频元素，首先我们得统计出每个元素的频数，这里可以使用哈希结构进行统计。统计完之后，我们遍历哈希的key列表，并用大小为k的小根堆进行维护，最后倒序输出小根堆的值就行了。
【哈希 + 小根堆】

class Solution {public int[] topKFrequent(int[] nums, int k) {// hashMap统计 + 小根堆维护Map<Integer,Integer> hm = new HashMap<>();for(int num : nums ) {hm.put(num,hm.getOrDefault(num,0) + 1);}// 特殊情况，k>= hm.size()if(k >= hm.size()) {return hm.keySet().stream().mapToInt(i->i).toArray();}// 小根堆维护PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> hm.get(a) - hm.get(b));for(int num : hm.keySet()) {heap.offer(num);if(heap.size() > k) {heap.poll();}}// 提取答案int[] res = new int[k];for(int i=0;i<k;i++) {res[i] = heap.poll();}return res;}
}

76. 数据流的中位数

求解思路： 这题我看了题解理解之后才写出来的，根本还是对数据结构的理解不到位。如果能想到用优先队列，这题其实很好做。
首先，定义两个优先队列，分别动态维护前半区元素和后半区元素，两者的堆顶极有可能产生中位数。存储前半区元素的堆采用最大堆，存储后半区元素的堆采用最小堆。在进行添加元素操作时，遵循以下判定步骤：

1. 首先判断该元素应该添加到前半区还是后半区 ---> 前半区为空 或者 当前元素小于前半区堆顶元素
2.  判断堆顶元素需不需要迁移

class MedianFinder {PriorityQueue<Integer> queMin; // 最大堆，保存较小的一半元素。堆顶是这一半中的最大值。PriorityQueue<Integer> queMax; // 最小堆，保存较大的一半元素。堆顶是这一半的最小值public MedianFinder() { // 初始化大顶堆和小顶堆queMin = new PriorityQueue<Integer>((a,b) -> (b-a));queMax = new PriorityQueue<>((a,b) -> (a-b));}public void addNum(int num) {// 前一半是空 | 当前元素小于堆顶元素// 将当前元素加入queMin，然后判断数量，是否需要堆顶迁移if(queMin.isEmpty() || num < queMin.peek()) {queMin.offer(num); // 如果说queMin - queMax >=2，为保证平衡，需要将queMin堆顶迁移加入到queMaxif(queMax.size() + 1 < queMin.size()) {queMax.offer(queMin.poll());}}else { // 反之加入后半区queMax.offer(num);// 同理判断后半区堆顶是否需要迁移if(queMax.size() > queMin.size()) {queMin.offer(queMax.poll());}}}public double findMedian() {// 如果左半区多，证明是奇数，堆顶为中位数// 否则是偶数，取两个堆顶的中间值if(queMin.size() > queMax.size()) {return queMin.peek();}return (queMin.peek() + queMax.peek()) / 2.0;}
}

77. 买卖股票的最佳时机

求解思路： 因为只能买卖一次，所以用两个变量遍历更新就行了。记录最小值min_profit，然后判断当前遍历到的元素中，是否存在利润大于max_profit，大于就进行更新。

class Solution {public int maxProfit(int[] prices) {int max_profit = 0;int min_profit = Integer.MAX_VALUE;for(int i=0;i<prices.length;i++) {if(prices[i] < min_profit) {min_profit = prices[i];}else if(prices[i] - min_profit > max_profit) {max_profit = prices[i] - min_profit;}}return max_profit;}
}

78.跳跃游戏

求解思路： 遍历数组的时候更新当前可达的最远距离。如果在遍历过程中发现当前位置比当前最远距离还大则说明不可达。

class Solution {public boolean canJump(int[] nums) {int n = nums.length;int k = 0;for(int i=0;i<n;i++) {// 如果当前点的距离比前面所能到达的最大距离还要大，则说明当前位置不可达if(i > k) return false;k = Math.max(k,i + nums[i]);}return true;}
}

79. 跳跃游戏Ⅱ

求解思路： 在上一题的基础上，对于每一次跳跃次数，都记录对应的最远跳跃距离，然后下一轮遍历中，在可达的位置中继续寻找下一次跳跃次数可以跳跃的最远距离。当更新到最远距离可达最后一位时，此时记录的跳跃次数就是最小跳跃次数。

class Solution {public int jump(int[] nums) {int n = nums.length;int ans = 0;int start = 0;int end = 1;while(end < n) {int maxDis = 0;for(int i=start ;i<end; i++) {// 能跳到的最远的距离maxDis = Math.max(maxDis, i+nums[i]);}start = end; // 下一次跳跃，可以选择的跳跃范围end = maxDis + 1; // 下一次跳跃最远的跳跃距离ans++;      // 计入跳跃次数}return ans;}
}

80. 划分字母区间

求解思路： 这题模拟一下案例就能大概清楚更新策略。只是策略优化的问题。
【策略一】

  • 首先最简单的想法，双指针st和ed，st指第一个字母，然后ed指最后一个字母。每一轮st，ed都去找对于st字母最后的位置，然后更新长度currlen，直到某一次st == currlen 时，说明前面的字母都匹配了。可以以 0 - 0 + currlen作为一个划分区间。
  • 但是这个策略很容易退化成O(n^2)，因为做了无用功，对于重复的字母，我们重复进行了ed指针移动寻找的操作，实际上，我们可以实现预处理出26个字母对应的最后的位置。这样更简单。也就是下面的终极版策略二：哈希 + 双指针 + 贪心

【哈希 + 双指针 + 贪心】

class Solution {public List<Integer> partitionLabels(String s) {// 一个比较好的想法// 首先预处理出每个字母的最后一个位置的下标是什么int len = s.length();int[] last = new int[26];for(int i=0;i<len;i++) {last[s.charAt(i) - 'a'] = i; // 处理每个字母的下标是什么}List<Integer> ans = new ArrayList<>();int st = 0, end = 0;for(int i=0;i<s.length();i++) {// 这里的思路是贪心，首先需要分割的长度是动态变化的// 具体的，例如ababcc，一开始i指向第一个a，end记录2// i++指向b，end更新到3// i++指向a，end不变// i++指向b，end不变，此时 i == end，说明之前的字母都匹配要求了，直接切割end = Math.max(end,last[s.charAt(i)-'a']);  // 这一步十分关键if(i == end) {ans.add(end - st + 1); // 记录长度st = end + 1; // 更新起始点}}return ans;}
}
http://www.xdnf.cn/news/670051.html

相关文章：

  • 纯C++ 与欧姆龙PLC使用 FINS TCP通讯源码
  • NSSCTF-[闽盾杯 2021]DNS协议分析
  • 为什么单张表索引数量建议控制在 6 个以内
  • InvokeAI 笔记， 简单了解一下 (生成图片，text2img )
  • MQTT over SSL/TLS：工业网关如何构建端到端加密的数据传输通道
  • MySQL 只知道表名不知道具体库？如何查询？information_schema入手
  • ssh 测试 是否可以连通docker 容器
  • Excel常用公式全解析（1）：从基础计算到高级应用
  • 如何理解UDP 和 TCP 区别 应用场景
  • 笔记： 在WPF中ContentElement 和 UIElement 的主要区别
  • 2025年土建施工员备考考试真题及答案
  • 数据库MySQL学习——day13（索引与查询优化）
  • gcc clang
  • FastMoss 国际电商Tiktok数据分析 JS 逆向 | MD5加密
  • 安全监测预警系统的核心价值
  • Jmeter一些元件使用的详细记录
  • VR 赋能病毒分离鉴定：开启微观探索新视界
  • 微软开源bitnet b1.58大模型，应用效果测评(问答、知识、数学、逻辑、分析)
  • 数据分析实战1（Excel制作报表）
  • 【NLP基础知识系列课程-Tokenizer的前世今生第五课】从静态到可学：Tokenizer 的自适应演化之路
  • LVS负载均衡群集
  • 语音识别算法的性能要求一般是多少
  • Day128 | 灵神 | 二叉树 | 反转二叉树的奇数层
  • 软件同步机制-Peterson解决方案 简单讲解
  • 攻防世界-你猜猜
  • js判断当前设备是否为移动端
  • camera_venc_thread线程获取高分辨率编码码流
  • Vue组件化
  • Rust 学习笔记：关于闭包的练习题
  • Flink系列文章列表