c++ 二分查找

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int INF=-(1e9+5);
int a[N]; 
int q[N]; // 存储不同长度的结尾的最小值
int n;

int main(){
    // 根据单调性进行二分查找, 时间复杂度O(nlogn)
    memset(a, 0x00, sizeof a);
    memset(q, 0x00, sizeof q);
    cin>>n;
    for(int i=0; i<n; ++i) cin>>a[i];
    int len=0; // 枚举不同长度
    q[0]=INF;
    for(int i=0; i<n; ++i){
        int l=0;
        int r=len;
        while(l<r){ // 找到小于a[i]的最大的数
            int mid=l+(r-l+1)/2;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len, r+1);
        q[r+1]=a[i];
    }

    cout<<len<<endl;

    return 0;
}

python 模拟单调栈

from typing import List
class Solution:
    def main(self, n:int, a:List[int]):
        st=[]
        for e in a:
            if not st or e>st[-1]:
                st.append(e)
            else:
                # 使用二分法查找到第一个大于等于e的元素位置, 并使用e替换该元素
                l, r=0, len(st)
                while l<r:
                    mid=l+(r-l)//2
                    if st[mid]<e: l=mid+1
                    else: r=mid
                st[l]=e
        return len(st)


if __name__=='__main__':
    n=int(input())
    a=list(map(int, input().split()))
    sol=Solution()
    print(sol.main(n, a))