Readme

955.Delete-Columns-to-Make-Sorted-II

我们考虑第一列。如果有任何相邻两行字符的关系是降序的，就意味着第一列我们必须删除。如果没有出现逆序，那么我们就可以保留第一列。

假设我们可以保留第一列，那么我们考虑第二列时，在判断相邻两行字符串A[i-1][0:1]和A[i][0:1]的关系时，如何高效地判断是否存在逆序呢？我们注意到，如果A[i-1][0]<A[i][0]，那么无论A[i-1][1]和论A[i][1]的关系如何，这两个字符串总是升序关系的。如果A[i-1][0]==A[i][0]，那么这两个字符串的关系就取决于A[i-1][1]和A[i][1]。至于A[i-1][0]>A[i][0]，那是不可能出现的，因为我们之前所做的任何删除列的操作就是为了保证每行的字符串是增序的。

所以我们维护一个数组p，p[i]=1表示第i行的字符串已经大于第i-1行的字符串，否则表示目前为止第i行的字符串完全等于第i-1行的字符串。这样我们只需要根据上一轮的p[i]、和这一列A[i-1][j]与A[i][j]两个字符的关系，就能判断是否维持了增序，并且记得更新p[i]。具体的是：

1. 如果p[i]=1，那么已经增序，不用判断。
2. 如果p[i]=0，且A[i-1][j]==A[i][j]，那么继续维持p[i]=0
3. 如果p[i]=0，且A[i-1][j]<A[i][j]，那么可以更新p[i]=1
4. 如果p[i]=0，且A[i-1][j]>A[i][j]，那么整个第j列都不能保留，同时p也不更新。