头像

tea321000

SZU




离线:16小时前


活动打卡代码 AcWing 830. 单调栈

tea321000
21小时前
#include<iostream>
using namespace std;
int n,tt=0,x;
const int N=1e5+10;
int nums[N],st[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        while(tt && st[tt]>=x)  tt--;
        cout<<(tt?st[tt]:-1)<<" ";
        st[++tt]=x;
    }
}



tea321000
21小时前
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        #ifdef _commet
        标准的单调栈题。做出的改动是把原来的nums数组分为query set的nums1以及support set的nums2。因此我们只要在第一次遍历时用hash
        储存nums2元素值以及其下一个最大元素的映射关系,在第二次遍历时用nums1进行查询即可。
        #endif

        stack<int> st;
        unordered_map<int,int> hash;//键:nums2的元素值nums[i] 值:nums2[i]的下一个最大元素
        for(int i=nums2.size()-1;i>=0;i--)
        {
            while(!st.empty() && st.top()<=nums2[i]) st.pop();
            hash[nums2[i]]=st.empty()?-1:st.top();
            st.push(nums2[i]);
        }

        vector<int> ans;
        for(int i=0;i<nums1.size();i++)
        {
            ans.push_back(hash[nums1[i]]);
        }
        return ans;
    }
};



class Solution {
public:
    int nextGreaterElement(int n) {
        #ifdef _commet
        这道题乍一看先入为主是单调栈题目,其实跟单调栈没啥太大关系,虽然也可以使用栈这个结构来做,但并没有什么优势。
        单调栈的优点在于遍历数组的同时输出或者用vector储存比当前遍历到的元素更大的下一个元素,而在此题中我们是要从右往左遍历,首先求得第一个递减的元素位置,
        然后将它与比它更大的最小数交换(如25432,2就是要找的这个位置,与比2更大的最小数3进行交换),最后再将右侧的序列翻转(即将3 5422转为3 2245),
        也就是说我们实际上要找的是比特定元素更大的元素,此时右侧序列虽然是单调的,但是并不能在初次遍历就将要求的结果输出或者储存
        (比如可能会出现265这种从右往左第一遍遍历时压根就找不到比2更大的数),因此并没有什么优势,跟自己
        从右往左再遍历一遍是一样的。当然,右侧序列第二次遍历从左往右遍历也是可以的,因为并不清楚找到的位置元素位于右侧序列的哪个位置,因此都是半斤八两。
        #endif
        stack<char> st;
        string s = to_string(n);
        int k=s.size()-1;
        while (k && s[k-1]>=s[k])
            k--;
        if(!k)
            return -1;
        for(int i=s.size()-1;i>=k;i--)
        {
            if(s[i]>s[k-1])
            {
                swap(s[k-1],s[i]);
                reverse(s.begin()+k,s.end());
                break;
            }
        }
        auto ans=stoll(s);
        if (ans > INT_MAX)
            return -1;
        return ans;

    }
};



题目描述

输入:循环数组
输出:从左往右遍历第一个比数组中对应位置元素大的数值

样例

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

算法1

(单调栈) $O(n)$

此题为单调栈类题目,其思路跟双指针类似,首先先思考暴力解法,然后再在暴力解法的基础上进行优化。
首先先不考虑循环数组,在简单的数组中,暴力解法的做法为两重循环$O(n^2)$。首先第一重循环遍历数组每个元素本身$i$,第二重循环再从$i+1$的位置往右遍历直到遍历到一个比该元素更大的数。然后我们可以观察到,假如数组中存在$j,k (j < k)$,而且$nums[j]>=nums[k]$,则无论如何都不会遍历到k而会在i到j中找到更大的数;假如在此区间内无法找到,也不会取$nums[k]$,因为此时$nums[i]>nums[j]>=nums[k]$。这就是单调栈单调的来源。

然后通过观察数组的遍历特点可以发现,当$i$的位置越靠近数组的末端,则越难找到比它大的数(因为右侧数的数量在减少)。当$i$就是最右端的数时,不能找到比他更大的数。因此,我们需要从右往左进行遍历;同时,由于我们储存数的顺序(即真正的遍历顺序)总是在题目要求的遍历的顺序的相反方向(即从右往左遍历时,先遍历到$k$再遍历到$j$,而在遍历到$k$时储存的数会在遍历$j$时释放),因此需要使用先进后出的栈结构来对相应的数进行储存,这样我们最先储存的数会在最后才被拿来与$i$做比较。

在回到题目本身,这个题目还加上了循环数组的限制,因此我们需要可以使用一个trick,即在原数组右侧再复制一份相同的数组再进行反向遍历,并在右半的$n$个数中不进行结果输出。这是因为假设数组中存在$l,m,n(l < m < n)$且$nums[m]>nums[n]>nums[l]$,而假设$n$右侧没有比它更大的数,则必定会通过循环找到满足条件的$m$,就等价于访问了右侧复制的一份数组中的元素。而$l$由于已经在$m$前访问过并不满足条件,就算再在数组后面复制一次也是没有用的;而就算$m$右侧还有比$m$更大的数,但因为我们只需要找第一个更大的数,因此也不需要访问。因此,只需要在右侧再复制一份数组,使得在从右往左遍历,遍历到左半时已经有完整遍历了右半数组所有元素的单调栈即可。

C++ 代码

stack<int> st;
vector<int> ans(nums.size());
nums.insert(nums.end(),nums.begin(),nums.end());
for(int i=nums.size()-1;i>=0;i--)
{
    while(!st.empty() && st.top()<=nums[i])//注意是小于等于而不是小于,不然会WA
    {
        st.pop();
    }
    if(i<nums.size()>>1)
    {
        if(st.empty())
            ans[i]=-1;
        else
            ans[i]=st.top();
    }
    st.push(nums[i]);
}
return ans;



class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        #ifdef _commet
        输入:循环数组
        输出:从左往右遍历第一个比数组中对应位置元素大的数值

        此题为单调栈类题目,其思路跟双指针类似,首先先思考暴力解法,然后再在暴力解法的基础上进行优化。
        首先先不考虑循环数组,在简单的数组中,暴力解法的做法为两重循环$O(n^2)$。
        首先第一重循环遍历数组每个元素本身$i$,第二重循环再从$i+1$的位置往右遍历直到遍历到一个比该元素更大的数。
        然后我们可以观察到,假如数组中存在$j,k(j<k)$,而且$nums[j]>=nums[k]$,则无论如何都不会遍历到k而会在i到j中找到更大的数;
        假如在此区间内无法找到,也不会取$nums[k]$,因为此时$nums[i]>nums[j]>=nums[k]$。这就是单调栈单调的来源。

        然后通过观察数组的遍历特点可以发现,当$i$的位置越靠近数组的末端,则越难找到比它大的数(因为右侧数的数量在减少)。
        当$i$就是最右端的数时,不能找到比他更大的数。因此,我们需要从右往左进行遍历;同时,由于我们储存数的顺序(即真正的遍历顺序)
        总是在题目要求的遍历的顺序的相反方向(即从右往左遍历时,先遍历到$k$再遍历到$j$,而在遍历到$k$时储存的数会在遍历$j$时释放),
        因此需要使用先进后出的栈结构来对相应的数进行储存,这样我们最先储存的数会在最后才被拿来与$i$做比较。

        在回到题目本身,这个题目还加上了循环数组的限制,因此我们需要可以使用一个trick,即在原数组右侧再复制一份相同的数组再进行反向遍历,
        并在右半的$n$个数中不进行结果输出。这是因为假设数组中存在$l,m,n(l<m<n)$且$nums[m]>nums[n]>nums[l]$,而假设$n$右侧没有比它更大的数,
        则必定会通过循环找到满足条件的$m$,就等价于访问了右侧复制的一份数组中的元素。
        而$l$由于已经在$m$前访问过并不满足条件,就算再在数组后面复制一次也是没有用的;
        而就算$m$右侧还有比$m$更大的数,但因为我们只需要找第一个更大的数,因此也不需要访问。
        因此,只需要在右侧再复制一份数组,使得在从右往左遍历,遍历到左半时已经有完整遍历了右半数组所有元素的单调栈即可。
        #endif
        stack<int> st;
        vector<int> ans(nums.size());
        nums.insert(nums.end(),nums.begin(),nums.end());

        for(int i=nums.size()-1;i>=0;i--)
        {
            while(!st.empty() && st.top()<=nums[i])//注意是小于等于而不是小于,不然会WA
            {
                st.pop();
            }
            if(i<nums.size()>>1)
            {
                if(st.empty())
                    ans[i]=-1;
                else
                    ans[i]=st.top();
            }
            st.push(nums[i]);
        }
        return ans;
    }
};


活动打卡代码 AcWing 829. 模拟队列

#include<iostream>
using namespace std;
const int N=100010; 
int q[N];
int h,t,m;
int main()
{
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        // cout<<op<<endl;
        if(op=="push")  cin>>q[t++];
        else if(op=="pop")   h++;
        else if(op=="empty")    cout<<(h==t?"YES":"NO")<<endl;
        else if(op=="query")    cout<<q[h]<<endl;
    }

}


活动打卡代码 AcWing 828. 模拟栈

#include<iostream>
using namespace std;
const int N=100010;
int st[N];
int m,cnt;
int main()
{
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        if(op=="push")  cin>>st[cnt++];
        else if(op=="pop")   cnt--;
        else if(op=="query")    cout<<st[cnt-1]<<endl;
        else if(op=="empty")    cout<<(cnt==0?"YES":"NO")<<endl;

    }

}


活动打卡代码 AcWing 632. 最小区间

class Solution {
public:
    struct IndexVec{
            int val;
            int row;//索引的行下标
            int col;//索引的列下标
            IndexVec(int val,int row,int col):
                val(val),row(row),col(col){}
    };
    struct valCmp
    {
        // 结构体小 取值比取引用更快
        bool operator() (IndexVec const a,IndexVec const b){
            return a.val > b.val;
        }
    };
    vector<int> smallestRange(vector<vector<int>>& nums) {
        priority_queue<IndexVec,vector<IndexVec>,valCmp> heap;//小顶堆
        vector<int> ans;
        int inter_max=INT_MIN;
        for(int i=0;i<nums.size();i++)
        {
            heap.push(IndexVec(nums[i][0],i,0));
            inter_max=max(inter_max,nums[i][0]);
        }

        while(!heap.empty())
        {
            auto tmp = heap.top();
            heap.pop();
            //有更小区间时更新(注意要先更新区间再push跟更新新值,因为此时堆里的是当前的区间右端点最大值,顺序一定不能搞反)
            if(ans.empty()||ans[1]-ans[0]>inter_max-tmp.val)
                ans={tmp.val,inter_max};
            if(tmp.col+1<nums[tmp.row].size())//这里注意不要漏了加1,否则会爆heap
            {
                heap.push(IndexVec(nums[tmp.row][tmp.col+1],tmp.row,tmp.col+1));
                inter_max=max(inter_max, nums[tmp.row][tmp.col+1]);
            }
            else break;
        }
        return ans;
    }
};



class Solution {
    #ifdef _commet
    k路归并两种做法,一种是转化成两路归并,一种是用小顶堆来做,两种都是O(nlogk)
    #endif
public:
    #ifdef _heap
    struct heapCmp{
        bool operator() (ListNode* a,ListNode *b)
        {
            return a->val > b->val; 
        } 
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode *,vector<ListNode *>, heapCmp> heap;
        auto ans = new ListNode(-1),tail = ans;
        for(auto l:lists)
            if(l)
                heap.push(l);
        while(!heap.empty())
        {
            auto tmp = heap.top();
            heap.pop();
            tail = tail->next = tmp;
            if(tail->next)//注意要判断next是否为空 否则会runtime error
                heap.push(tail->next);
        }
        return ans->next;
    }
    #endif
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)//注意函数形参为ListNode*而不是vector<ListNode*>
    {
        auto ans=new ListNode(-1),tail=ans;
        while(l1!=NULL && l2!=NULL)
        {
            if(l1->val > l2->val)
            {
                tail = tail->next = l2;
                l2 = l2->next;
            }
            else
            {
                tail = tail->next = l1;
                l1 = l1->next;
            }
        }
        tail->next=l1!=NULL?l1:l2;
        return ans->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return NULL;
        if (lists.size() == 1)
            return lists[0];

        int mid= lists.size()/2;
        vector<ListNode*> k_left = vector<ListNode*>(lists.begin(),lists.begin()+mid);
        vector<ListNode*> k_right =vector<ListNode*>(lists.begin()+mid, lists.end());
        ListNode* l = mergeKLists(k_left);//通过递归函数本身将vector<ListNode *>转化成ListNode*求两路归并
        ListNode * r = mergeKLists(k_right);
        return mergeTwoLists(l,r);
    }

};



题目描述

输入:二维数组,每行为课程持续上课时间t以及关闭时间d
输出:可以修的最大课程数

样例

见原题

算法1

(贪心) $O(nlogn)$

状态表示:
贪心题,首先从直觉开始考虑,完成课程时倾向于先完成关闭时间更早也就是deadline更早的课程。
因此首先将课程任务按关闭时间从小到大进行排序。

$f(i)$:考虑按关闭时间排序后前i个课程的所有合法方案数量
属性:数量

状态计算:
排完序之后,再根据题目要求,我们需要选择可以修最大课程数的方案,因此需要满足:1、选的个数最多。但这样还不够,考虑到贪心转移的性质,我们必须在每一步都选择局部最优的子方案,否则即使在当前状态下为数量最优,在转移到下一状态后就可能错失最优解,因此在满足1的基础上,还需要满足:2、总用时最小(每种用时个数相同)。这样才能既保证选择课程数量最多又不会导致在转移的过程中用时过大错过最优解,选择局部最优的方案集合。之所以要令每种用时个数相同,是为了节省记录状态的数量。

接下来进行具体转移的计算。
当可以插入新课程$i$时,$$f(i)=f(i-1)+1$$ 此时满足:
1、选的个数最多,因为可以选的时候总是选择他加进去最好;
2、总用时最小(每种用时个数相同),因为第i个课程的用时是固定的,因此无法改变,
只能改变前$i-1$个课程时间的总和。又由于我们前面假设时取得是满足总用时最小的方案集合,$f(i-1)$的总用时也是最小的,因此$f(i)$也满足总用时最小。

当不可以插入新课程$i$(插进来会导致总时长超过课程关闭时间)时,$$f(i)=f(i-1)$$ 满足:1、选的个数最多。因为此时大不了就不学$i$,学的课程数量与之前保持一致。
对于2、总用时最小(每种用时个数相同),我们可以先假设把第$i$个课程加进来,加进来之后再去掉所有加进来的课程中持续上课时间$t$最大的那个课程(这个课程有可能是第$i$个课程,也有可能是前面的$i-1$个课程之一)来满足在不改变课程数量的同时,总用时最小。因为我们的$f(i-1)$方案集合是满足总时长要求的,因此在加进来第$i$个课程后再去掉持续时长最大的一个课程,只会使得$f(i)$的总时长小于等于$f(i-1)$(在去掉第$i$个课程或与其时长相等的课程时相等)(当存在多个最大持续时长时,去掉任意一个也并不会影响我们的最优解数量)

C++ 代码

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        //使用lambda函数进行sort
        sort(courses.begin(),courses.end(),[](vector<int> &c1,vector<int> &c2){
            return c1[1]<c2[1];
        });
        //大顶堆,小顶堆为priority_queue<int,vector<int>,greater<int>> heap;
        priority_queue<int> heap;
        //总时长
        int t=0;
        for(auto &c:courses){
            //根据前面分析 无论怎样先假设把我们的i课程插入
            t+=c[0];
            heap.push(c[0]);
            if(t>c[1])//总时长超过课程关闭时间
            {
                t-=heap.top();
                heap.pop();
            }
        }
        return heap.size();
    }
};