單調(diào)棧

• 單調(diào)棧應(yīng)用場景：找當(dāng)前元素左邊/右邊比當(dāng)前元素大/小的第一個(gè)元素
• 什么是單調(diào)棧：保證棧里面的元素遞增/遞減（需要自己定義）
• 棧內(nèi)保存什么：存入下標(biāo)
• 如何比較大小：棧和數(shù)組做映射
• 遞增？遞減？：取決于應(yīng)用場景
  • 遞增：求當(dāng)前元素左邊/右邊比他大的第一個(gè)元素
  • 遞減：求當(dāng)前元素左邊/右邊比他小的第一個(gè)元素
• 單調(diào)棧的作用：記錄存放遍歷過的元素，存放的同時(shí)進(jìn)行排序

739. 每日溫度

• 不需要倒序遍歷，正序遍歷，存入
• 注意棧內(nèi)存入的是元素下標(biāo)而不是元素的值
• 當(dāng)前元素比?？诖?#xff0c;則彈出?？谠?#xff0c;記錄該元素結(jié)果；循環(huán)該過程直到棧為空
• 當(dāng)前元素比?？谛?#xff0c;則壓入元素，不記錄
• 最后遍歷結(jié)束，但是棧內(nèi)的元素沒有找到比其更大的，則賦零

496.下一個(gè)更大元素①

• 可以在上一題的基礎(chǔ)上做

• 對(duì)于兩個(gè)沒有重復(fù)元素的數(shù)組（一個(gè)為另一個(gè)子集），可以用map來做映射

• unordered_map<int, int> umap;  //key，下標(biāo)元素；value，下標(biāo)
  for(int i = 0; i<nums1.size(); i++) umap[nums1[i]] = i;//使用
  if(umap.count(nums2[st.top()]) > 0){   //查看map中是否存在這個(gè)元素int index = umap[nums2[st.top()]]; //查詢?cè)撛貙?duì)應(yīng)的下標(biāo)result[index] = nums2[i];
  }