Paint the Digits

​​C - Paint the Digits​​

思路：這道題就隻需要利用單調棧，将整個數組掃一遍，求得的最後的棧内元素（要求全部小于非棧内元素）的顔色為1，其餘為2

那麼怎麼實作呢？求最後的棧内元素（要求全部小于非棧内元素）的方法：用一個變量記錄下最小的被交換的棧元素（這裡需要将由于元素相等而交換的情況派除在外）

int first=inf;

for(int i=1;i<=n;++i)

{

while((!s.empty())&&s.top()>=a[i])

{

if(s.top()!=a[i]) //将由于元素相等而交換的情況派除在外

first=min(fi,s.top());

s.pop();

}

s.push(a[i]);

}while(s.top()>fi&&fi&&(!s.empty())) //最後的棧内元素要求全部小于非棧内元素

s.pop();

然後就是考慮不存在的情況，将棧内元素全部标記成1之後，在标記棧外元素的時候，分别比較前後兩個數的大小，若後面的比前面的小，則不存在

代碼：

// Created by CAD on 2019/9/15.
#include <bits/stdc++.h>

#define fi first
#define inf 0x3f3f3f3f
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;

stack<int>s;
const int maxn=2e5+5;
int a[maxn];
int t[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;  cin>>T;
    while(T--)
    {
        mst(t,0);
        while(!s.empty()) s.pop();
        int n;cin>>n;
        string str;
        cin>>str;
        for(int i=1;i<=n;++i)
            a[i]=str[i-1]-'0';
        int first=inf;
        for(int i=1;i<=n;++i)
        {
            while((!s.empty())&&s.top()>=a[i])
            {
                if(s.top()!=a[i])
                first=min(fi,s.top());
                s.pop();
            }
            s.push(a[i]);
        }
        while(s.top()>fi&&fi&&(!s.empty())) s.pop();
        for(int i=n;i>=1;--i)
            if(a[i]<s.top()) s.pop(),t[i]=1;
            else if(a[i]==s.top()) t[i]=1;
        bool flag=true;
        int temp=0;
        for(int i=1;i<=n;++i)
            if(!t[i])
            {
                if (a[i]<temp)
                {
                    flag=false;
                    break;
                } else t[i]=2,temp=a[i];
            }
        if(flag)
        {
            for(int i=1;i<=n;++i) cout<<t[i];
            cout<<endl;
        }
        else cout<<'-'<<endl;
    }
    return 0;
}