旅游网站建设方,建设厅焊工证在哪里办,Wordpress一直刷不出,打不开网站怎么办单调栈基础
什么时候使用单调栈#xff1a;通常是一维数组#xff0c;要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置#xff0c;此时我们就要想到可以用单调栈了
单调栈的作用#xff1a;使用栈来记录已经遍历过的元素 使用单调栈前需要明确两点…单调栈基础
什么时候使用单调栈通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了
单调栈的作用使用栈来记录已经遍历过的元素 使用单调栈前需要明确两点 1、单调栈中存放的元素是什么 一般存放的是元素的下标如果需要使用值可以通过下标获取 2、单调栈里的元素是递增还是递减的 如果要寻找比自己大的元素则从栈顶到栈底应该是递增的 如果要寻找比自己小的元素则从栈顶到栈底应该是递减的 739. 每日温度
本题求的是每个元素左边的第一个比自身大的元素所以单调栈从栈顶到栈底应该是递增的 根据单调栈的定义使用时要根据当前元素与栈顶元素的大小关系做好情况分类 情况1——当前元素小于栈顶元素当前元素直接入栈满足从栈顶到栈底递增的定义情况2——当前元素等于栈顶元素当前元素直接入栈按照题意求的是比自身大而非大于等于自身也满足从栈顶到栈底递增的定义情况3——当前元素大于栈顶元素此时当前元素就是栈顶元素左边第一个比自身大的值弹出栈顶并记录结果不断弹出直至当前元素小于等于栈顶元素 vectorint dailyTemperatures(vectorint temperatures) {stackint st;vectorint ans(temperatures.size(), 0);st.push(0);for (int i 1; i temperatures.size(); i) {// 情况1当前元素小于等于栈顶元素元素下标入栈if (temperatures[i] temperatures[st.top()])st.push(i);// 情况2当前元素大于栈顶元素当前元素就是栈顶元素后的第一个更高温度else {while (!st.empty() temperatures[i] temperatures[st.top()]) {ans[st.top()] i - st.top();st.pop();}st.push(i);}}return ans;
}496.下一个更大元素 I
本题可以拆分为两个问题
如何在nums2中找到下一个更大元素? —— 使用单调栈如何将nums2中的元素映射到nums1? —— 使用哈希表创建索引
将问题分解好这道题就不难了两个子问题的处理都比较简单其中单调栈的写法和上一题差不多
vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { unordered_mapint, int record;// 将nums1的 {值, 下标} 存入哈希表用于nums2的映射for (int i 0; i nums1.size(); i) {record.insert({ nums1[i], i });}vectorint ans(nums1.size(), -1);stackint st;// 由于没有重复元素所以栈中能直接存放元素值st.push(nums2[0]);for (int i 1; i nums2.size(); i) {if (nums2[i] st.top())st.push(nums2[i]);else {while (!st.empty() nums2[i] st.top()) {// 使用哈希表在nums1中进行索引auto it record.find(st.top());if (it ! record.end())ans[it-second] nums2[i];st.pop();}st.push(nums2[i]);}}return ans;
}
