最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

每日热门：【算法训练营day58】LeetCode739. 每日温度 LeetCode496. 下一个更大元素

来源：博客园


【资料图】

LeetCode739. 每日温度

题目链接：739. 每日温度

独上高楼，望尽天涯路

直接看题解。

慕然回首，灯火阑珊处

单调栈一般用来解决一维数组，任意一个元素的右边或者左边第一个比自己大或者小的元素。本质上是用空间换时间，用一个栈来记录我们遍历过的元素。

class Solution {public:    vector dailyTemperatures(vector& temperatures) {        stack st;        vector result(temperatures.size(), 0);        for (int i = 0; i < temperatures.size(); i++) {            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {                result[st.top()] = i - st.top();                st.pop();            }            st.push(i);        }        return result;    }};

LeetCode496. 下一个更大元素

题目链接：496. 下一个更大元素

独上高楼，望尽天涯路

和上一道题很相似。

慕然回首，灯火阑珊处

和上一道题相比，思路是一样的，但是对代码能力要求更高，需要熟练使用单调栈和哈希表。

哈希表的作用就是查看nums2中的元素是否在nums1中出现过，如果出现过就返回其在nums1中的下标。

class Solution {public:    vector nextGreaterElement(vector& nums1, vector& nums2) {        stack st;        vector result(nums1.size(), -1);        if (nums1.size() == 0) return result;        unordered_map umap; // key:下标元素，value：下标        for (int i = 0; i < nums1.size(); i++) {            umap[nums1[i]] = i;        }        st.push(0);        for (int i = 1; i < nums2.size(); i++) {            while (!st.empty() && nums2[i] > nums2[st.top()]) {                if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素                    int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标                    result[index] = nums2[i];                }                st.pop();            }            st.push(i);        }        return result;    }};

关键词： 灯火阑珊处 独上高楼 望尽天涯路