leetcode 769, 768 最多能完成排序的块 单调栈建模

768和769本质相同，都是单调栈
为什么能用单调栈？
核心思路：块的最大值小于等于右边所有元素
隐藏边界：块的边界会通过较小元素进行破坏，从而继续保持单调性。

classSolution{public:intmaxChunksToSorted(vector<int>&arr){vector<int>st{-1};for(autonum:arr){intmx=num;while(num<st.back()){mx=max(mx,st.back());st.pop_back();}st.push_back(mx);}// for(auto t: st)printf("%d ", t);returnst.size()-1;}};

首先是769，这个题是很简单的，只要看最大元素和索引关系即可。

classSolution:defmaxChunksToSorted(self,arr:List[int])->int:result,bad=0,-1foriinrange(len(arr)):bad=max(bad,arr[i])ifbad<=i:result+=1bad=-1returnresult

768则是这个题的终极复杂形式，数组里数据不再是简单的0-n，变成任意数据，还可以重复。
解法一：O(NlogN)
思路：转化为第一题的思路，看到这个数一定要知道这个数在数组的排序位置，这样O(N)就能解决（除去排序的NlogN）。
可以先排序，找到各个元素对应的位置，再扫一遍即可。对于重复元素，存一个优先队列，需要的时候排出来最小的。

pos=sorted(range(len(arr)),key=lambdax:arr[x])

一个很奇怪的地方，就是python本身的bug，上述代码是无法返回正确的排序后索引的，可能是python版本的问题。所以这里要自己对数组排序后再自己遍历一遍手动得到索引，代码如下：

fromqueueimportPriorityQueueclassSolution:defmaxChunksToSorted(self,arr:List[int])->int:# get sorted idxnum2q={}sorted_arr=sorted(arr)foridx,numinenumerate(sorted_arr):ifnumnotinnum2q:num2q[num]=PriorityQueue()num2q[num].put(idx)# base algorithmresult,bad=0,-1foridx,numinenumerate(arr):real_pos=num2q[num].get()bad=max(bad,real_pos)ifbad<=idx:result+=1bad=-1returnresult

解法二：O(N)
这个解法有点dp的意思。如果一个块没法判断它是否是一个可分割块，就看他后面的元素。如果后面的元素有比他小的，那就不是，如果没有，那就是。

classSolution:defmaxChunksToSorted(self,arr:[int])->int:stack=[]fornuminarr:ifstackandnum<stack[-1]:tmp=stack.pop()whilestackandnum<stack[-1]:stack.pop()stack.append(tmp)else:stack.append(num)returnlen(stack)

这里有两个小技巧，一个是用if list可以判断list是否为空（很重要！！！）第二个是list.pop()可以直接返回列表尾部元素。
这里算法用到了单调栈的思想，看似栈内大的元素被排出去了，实际只是保留了每个块最大值，消除了无法独立成块的最大值。