70-76-堆、贪心算法

LeetCode 热题 100

本文存储我刷题的笔记。

---

堆

70. 中等-数组中的第K个最大元素

71. 中等-前K个高频元素

72. 困难-数据流中的中位数

贪心算法

73. 简单-买卖股票的最佳时机

我的思路

• 思路：从左到右遍历每个元素，每次都更新最小值和最大值，并不断更新最大利润。
• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。
• 时间104ms(59.40%)，内存91.48MB(53.42%)。

class Solution {
public:int maxProfit(vector<int>& prices) {// 排除特殊情况：只有一天int len = prices.size();if(len<=1){return 0;}// 遍历所有所有天数int p_max{prices[0]}, p_min{prices[0]}, profit{0};for(int i=1; i<len; i++){p_min = std::min(p_min, prices[i]); // 更新下限p_max = std::max(p_min, prices[i]); // 更新当前下限后的上限profit = std::max(profit, p_max-p_min); // 更新最大利润}return profit;}
};

官方思路一：一次遍历

• 思路：保存以往的最低点，计算今天能获利多少，遍历一次即可完成。

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。

• 时间84ms(97.06%)，内存91.39MB(77.65%)。

class Solution {
public:int maxProfit(vector<int>& prices) {int minprice = prices[0]; // 以往的最低点int maxprofit = 0;        // 最大利润// 遍历每一个元素for (int price: prices) {maxprofit = max(maxprofit, price - minprice); // 更新最大利润minprice = min(price, minprice);              // 更新以往最低点}return maxprofit;}
};

74. 中等-跳跃游戏

75. 中等-跳跃游戏II

76. 中等-划分字母区间

我的思路

• 思路：

• 时间??ms(??%)，内存??MB(??%)。

官方思路：

• 思路：

• 时间??ms(??%)，内存??MB(??%)。