Readme

1504.Count-Submatrices-With-All-Ones

此题的数据量非常小，可以o(MMN)暴力解决。但是有更巧妙的o(MN)做法。

和85相同的技巧，我们逐行处理，更新以第i行为底座的histogram。然后逐列处理histogram里面的柱子，我们试图用单调栈来判定：以第j根柱子为右边界的矩形有多少个。

我们想象，如果histogram里面的柱子都是递增的。假设以第j-1根柱子为右边界的矩形有count[j-1]个，并且第j根柱子比第j-1根的高，那么将这些count[j-1]个矩形向右延伸靠到第j根柱子上的话，都会变成有效的count[j]。此外，我们只需要再计数仅包括第j根柱子本身的矩形，故count[j] = count[j-1] + nums[j].

当我们如果遇到第j根柱子矮于第j-1根柱子呢？那么并不是所有count[j-1]个矩形都可以继承并延伸成为j的一部分。我们需要退回那些“超高”的部分，即高度差为nums[j]-nums[j-1]的这部分矩形我们要吐出去，剩余的矩形才能继承成为j的一部分。此外，我们发现，如果nums[j-2]也高于nums[j]的话，这样的回吐过程还要继续进行下去。

于是这一切都提示我们用单调栈。

使用单调栈时特别要注意，假设栈顶元素的index是p1，次栈顶元素的index是p2，p1与p2不一定连着的。这是因为之前p1将(p2,p1)之间的元素都逼出栈了。但这并不是说中间没有柱子了，而是意味着，(p2,p1)之间存在着与p1等高的柱子。所以p1退栈的时候，需要退出的矩形数目其实是(p1-p2)*(nums[p1]-nums[j]).

退栈之后记得别忘了算上nums[j]（也就是仅包含第j根柱子的矩形），并将j压入栈顶。