淘宝官方网站主页,网站建设基本流程流程图,网站建设及使用方案,域名服务器名词解释LeetCode 热题 100 文章目录 LeetCode 热题 100堆70. 中等-数组中的第K个最大元素71. 中等-前K个高频元素72. 困难-数据流中的中位数 贪心算法73. 简单-买卖股票的最佳时机74. 中等-跳跃游戏75. 中等-跳跃游戏II76. 中等-划分字母区间 本文存储我刷题的笔记。 堆
70. 中等-数组…LeetCode 热题 100 文章目录 LeetCode 热题 100堆70. 中等-数组中的第K个最大元素71. 中等-前K个高频元素72. 困难-数据流中的中位数 贪心算法73. 简单-买卖股票的最佳时机74. 中等-跳跃游戏75. 中等-跳跃游戏II76. 中等-划分字母区间 本文存储我刷题的笔记。 堆
70. 中等-数组中的第K个最大元素
71. 中等-前K个高频元素
72. 困难-数据流中的中位数
贪心算法
73. 简单-买卖股票的最佳时机 我的思路 思路从左到右遍历每个元素每次都更新最小值和最大值并不断更新最大利润。时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。时间104ms(59.40%)内存91.48MB(53.42%)。 class Solution {
public:int maxProfit(vectorint prices) {// 排除特殊情况只有一天int len prices.size();if(len1){return 0;}// 遍历所有所有天数int p_max{prices[0]}, p_min{prices[0]}, profit{0};for(int i1; ilen; 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(n) O(n)。 空间复杂度 O ( 1 ) O(1) O(1)。 时间84ms(97.06%)内存91.39MB(77.65%)。 class Solution {
public:int maxProfit(vectorint 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(??%)。
