madness of window managers 1

搞了几个月的窗口管理器，不得不说这行真乱。即使有icccm和wm-spec这样的协议存在，但是每个wm在实现的时候也未必完全按照规范来。而有的时候大概
是因为协议本身有些地方说的就比较模糊或者设计得不够合理，导致各个wm的行为出现不一致。
比如wm-spec里提到的
_NET_WORKAREA这个属性。xfwm4，compiz和mutter在同一个多屏幕配置下出现了完全不同的设置，导致在一些场景下有些窗口出现的位置出现奇怪的反直觉。

给个具体实例：
一个多屏环境，有三个工作区，有一个dock程序设置了STRUTS，数据分别是：

xrandr信息：
LVDS1 connected primary 800x600+0+0
DP1 connected 1440x900+800+0

dock设置的struts信息：
_NET_WM_STRUT_PARTIAL(CARDINAL) = 0, 0, 0, 362, 0, 0, 0, 0, 0, 0, 49, 725

在这样一个配置下，三个wm给出的属性是：

xfwm4 _NET_WORKAREA(CARDINAL) = 0, 0, 2240, 538, 0, 0, 2240, 538, 0, 0, 2240, 538, 0, 0, 2240, 538

compiz _NET_WORKAREA(CARDINAL) = 0, 0, 2240, 900

mutter _NET_WORKAREA(CARDINAL) = 725, 0, 1515, 900, 725, 0, 1515, 900, 725, 0, 1515, 900

从我个人角度看mutter是最合理的。首先三个工作区都有数据，避开了struts所占据的位置，并且使工作区面积最大化
（1515x900 > 2240x538)，xfwm4其次，compiz最离谱，完全不遵守协议。尽管mutter看起来最符合规范，但是却导致有些程序在
放置窗口时出现了问题。比如eog这样的程序，在弹出下拉菜单时会尊重_NET_WORKAREA的设置，所以
它主动将弹出菜单强制放置在这个范围内（比如（734,126）），即使eog主窗口的位置可能不在此范围内（比如在LVDS1的（0,102）位置）。这导致视觉上，弹出菜单不在鼠标点击的位置弹出，反而偏移了很远。
而在compiz和xfwm4上此时却没有问题，因为它们的WORKAREA从（0,0）这个位置开始。有趣的是，如果双屏的分辨率稍作修改，变成如下所示：

LVDS1 connected primary 1366x768+0+0
DP1 connected 1440x900+1366+0

mutter上就不会出问题了。因为根据使工作区面积最大化的算法，_NET_WORKAREA变成了如下数据：

_NET_WORKAREA(CARDINAL) = 0, 0, 2806, 698, 0, 0, 2806, 698, 0, 0, 2806, 698

但是这并不是说xfwm4上eog就不能出现类似现象，只要精心调整两屏的位置和分辨率，这个情况也能
构造出来。主要原因还是wm-spec里对_NET_WORKAREA的描述并不是很精确，wm在实现时有很大的
自由性。像_NET_WORKAREA这种情况在wm的世界里似乎有很多。

如何实现简单的POSIX信号处理

这是一篇关于POSIX信号实现机制的文章，主要是基于自己的思考、sos实现以及对早期linux内核（0.11和1.0版本）的分析。这里谈论的是古老的实现方式，我不确定是否还有系统在使用类似的方法。因为这里的实现技术具有很多缺陷，在描述实现细节之后我们再来看看一些现代linux的更好的实现方式。

我将不会描述什么是信号以及如何使用信号，这方面最好的参考是UNIX环境高级编程，也可以参考《Linux Programming Interface》这本书。信号的生命周期包括生成（generate），送达（deliver）。在这篇文章里我把重点放在deliver的实现上，更精确地说，我要通过一个具体而微的简单内核的实现来描述操作系统内核是怎么调用用户空间提前设置好的信号处理函数的。

我们都知道操作系统内核和用户程序分别运行于独立的特权级。用户空间通过受限的方式（系统调用、文件读写等）访问内核资源。用户通过使用signal或sigaction系统调用来设置信号的自定义处理函数。我们都知道，POSIX信号是异步执行的（不考虑实时信号），发送信号的时刻与该信号对应的处理可能会相隔很远，具体要看是什么信号以及进程所处的状态。当信号最终被送达目标进程并被处理时，内核并不能直接调用自定义的信号处理函数，因为它所处的内存页是用户级的（准确的说其实是可以的，高特权级的代码是可以调用低特权级代码的，但由于各种安全原因并不会直接调用）。为了执行一段用户态的代码，内核需要使用一些技巧。

在实现内核实施用户自定义函数时，需要考虑一些问题。首先，这种调用肯定是破坏性的。因为内核和函数处于不同的特权级（自然使用到的栈空间也不一样），没有简单的caller/callee关系，调用也不是通过通常的call指令发生的。所以要有一种方法保证执行信号处理函数前后的现场是一致的。另外，信号处理函数是可以嵌套的，用户完全可以在信号处理函数内部发送信号。我们设计的方案必须能处理这种情况。

在x86系统下，如果代码要从高特权级（内核）跳转到一个低特权级（用户态）的代码段最基本的方法是手工构造一个iret调用。基本上这是所有中断服务例程返回用户态的方法。而我们实现处理函数的执行就是利用了这个iret指令。基本思路是：

iret指令返回用户态时会从内核栈中弹出五个数据，分别是用户态的ss、esp、eflags，cs、eip。eip是执行系统调用的中断指令的下一条指令的地址。在正常情况下，iret将返回到eip地址处继续用户程序的执行。如果我们在iret执行前，修改了内核栈中对应eip位置的值，让其指向用户先前设置的信号处理函数的地址，那么iret返回后不就执行信号处理函数了吗。但是事情还没完，函数执行时，我们需要给它提供一个参数。而且这个函数执行完成后会返回哪里呢？合理的情况下当然是返回修改eip前，iret应该返回的位置。这么一来就清楚了，我们需要手动为信号处理函数在用户态的栈空间里建立一个栈帧，设置函数的参数和返回地址。这里有一个细节问题，那就是当我们手动建立栈帧时，势必修改了用户esp的值，而且信号处理函数有可能改动了某些寄存器的值。我们在处理函数ret之前要把现场恢复到原始状态，就好像iret是直接返回的一样。

根据上面的描述，我们来看一个具体的实现，也就是sos的handle_signal。首先要说明的，因为内核在何时deliver（即检测当前进程是否有pending的信号等待并处理）有很大的灵活性。比如linux会在每次时钟中断时检测，同时在任何中断请求结束并返回用户空间前也会检测。目前sos的实现是只在系统调用返回用户空间前检测。

在实现上面的机制时，要如何保存和恢复现场，如何设置信号处理函数的调用环境等，有很多的选择性。我所使用的方法基本上跟linux 0.11版本一样（后来我看过几个其他的简单内核，其思路基本也是一样的）。这个函数目前实现不完整，但是表达了基本的要素。当检查到用户设置了自定义的处理函数时，就着手构造一个处理函数执行的环境。这段代码不长，我直接贴出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
uint32_t oesp = regs->useresp;
uint32_t* ustack = (uint32_t*)((char*)oesp - sizeof(sigcontext_t));
sigcontext_t ctx;
ctx.eax = regs->eax;
ctx.ebx = regs->ebx;
ctx.ecx = regs->ecx;
ctx.edx = regs->edx;
ctx.esi = regs->esi;
ctx.edi = regs->edi;
ctx.ebp = regs->ebp;
ctx.uesp = regs->useresp;
ctx.eip = regs->eip;
ctx.sig_mask = current->sig.blocked;
memcpy(ustack, &ctx, sizeof(sigcontext_t));

// trampoline code
// movl SYS_sigreturn, %eax
// int $0x80
// ret
char* code = (char*)ustack - 1;
*code-- = 0xc3; // ret
*code-- = 0x80;
*code = 0xcd; // int $0x80
code -= 4;
*(uint32_t*)code = SYS_sigreturn;
code--;
*code = 0xb8;

signal_dbg("save at 0x%x, code at 0x%x, new eip 0x%x\n",
        ustack, code, handler);
ustack = (uint32_t*)code - 2;
ustack[0] = (uint32_t)code;
ustack[1] = sig;
regs->eip = (uint32_t)handler;
regs->useresp = (uint32_t)ustack;

代码很短，但是干了很多事情，我们分几个部分来看：

  • 首先是保存原始环境。regs指向内核栈iret返回前的中断上下文。我在用户栈的栈顶位置开辟一个空间来保存（sigcontext_t结构）。
  • 然后是一段硬编码的x86 32位代码，如注释所示，它构造了一个函数，这个函数的功能是执行一个系统调用SYS_sigreturn。如果你去看sys_sigreturn的代码，你就知道它是与之相对的用来恢复现场的系统调用。可以看出来，这段代码存放在用户栈中。如图所示：
  • 最后修改了regs的eip，使其指向信号处理函数。而useresp指向新的ustack位置。ustack的栈底最后两个位置一个是信号处理函数的参数（即信号值）以及返回地址。返回地址指向了硬编码的那段代码的第一条指令的地址。于是在信号处理函数执行完成后，会跳转到上面的那段代码，该代码立即执行一个系统调用来恢复被信号处理函数改变的现场。如图所示：

在信号处理函数执行完成后，会返回到并执行栈中的trampoline，从而触发一个对sigreturn的系统调用。陷入内核后，此时的栈情况如图所示：

sigreturn的工作就是把保存在用户栈中上下文恢复到内核栈中对应的位置。注意，恢复后，regs里的eip指向了被信号处理函数打断的系统调用的返回地址。

需要注意的是，上面的方法是不安全的，而且也不具有可移植性。现代的操作系统应该不会允许用户栈具有可执行权限（在linux下可以用cat /proc/self/maps看看[stack]区域）。而硬编码指令的做法也无法在不同的体系结构下运行。所以现代linux在恢复信号处理后的现场时，采用了其他技术（比如利用vdso和c库配合），这个需要另外一篇文章详细描述。

PS：这有一个方便的查询linux系统调用的网址，挺方便的。

PPS：sos是我自己写的一个简单内核，极度不完善。

'leetcode: longest consecutive sequence'

It blocke me at first for a while, then suddenly I came up with an idea:

first build a map, whose key is the beginning of consective seq and value is end of seq, which is initially equals to the beginning (length of seq is 1).

then we walk through the map, during the walking, join the neighbour seqs and erase from map so we won’t visit twice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            int res = 0;
            unordered_map<int, int> h;
            for (int i = 0, n = num.size(); i < n; i++) {
                h[num[i]] = num[i];
            }

            auto x = h.begin();
            unordered_map<int, int>::iterator i;            
            while (x != h.end()) {
                auto v = x->second;
                while ((i = h.find(v+1)) != h.end()) {
                    x->second = h[v+1];
                    v = h[v+1];
                    h.erase(i);                                        
                }
                res = max(res, v-x->first+1);
                x++;
            }
            return res;
        }
};

The same idea can be described in a more concise way in one pass:

This time we build the map on the way. The key is the num, but the value means the length of the sequence which has the key as one of its borders.

we iterate each value in the num array, if it resides in the map, just ignore. Else, we find the two adjcent sequences from left and right, and combine them into one seq. after that, we update the value of the borders of the new seq to the length of the seq.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution2 {
    public:
        int longestConsecutive(vector<int> &num) {
            int res = 0;
            unordered_map<int, int> h;
            for (auto& x: num) {
                if (!h[x]) {
                    h[x] = 1 + h[x+1] + h[x-1];
                    if (h[x+1]) h[h[x+1]+x] = h[x]; 
                    if (h[x-1]) h[x-h[x-1]] = h[x];
                }
                res = max(h[x], res);
            }

            return res;
        }
};

leetcode: text justification

I don’t know why it marked as hard since there is no need to messing around with strings or arrays. for clarity, I use two pass below, actually it can be done with one pass concisely.

The idea is:

  • group strings according to if they fit into the same line
  • then caculate space between words in each line and generate compound string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public:
        vector<string> fullJustify(vector<string> &words, int L) {
            //pack
            vector<vector<string>> groups;
            while (words.size()) {
                int len = 0;
                vector<string> g;
                while (words.size() && words.front().size() + len <= L) {
                    g.push_back(words.front());
                    len += words.front().size() + 1;
                    words.erase(words.begin());
                }
                if (g.size()) groups.push_back(g);
            }

            //adjust
            int j = 0;
            for (auto& x: groups) {
                string s = x.front();
                if (x.size() == 1) s += string(L - s.size(), ' ');
                else {
                    auto k = L;
                    for (auto& i: x) k -= i.size();
                    auto d = k / (x.size()-1), r = k % (x.size()-1);

                    if (j == groups.size()-1) {d = 0; r = x.size(); }
                    for (int i = 1; i < x.size(); i++) {
                        s += string((i <= r ? (d+1) : d), ' ') + x[i];
                        k -= d+(i<=r?1:0);
                    }
                    if (k) s += string(k, ' ');
                }
                words.push_back(s);
                j++;
            }

            return words;
        }
};

leetcode: Copy List with Random Pointer

This problam inspires a lot of interesting solutions.

we can create the new list by iterating the origin list. when the origin node has a random pointer. we spawn a new node and record it in a map. the key of map is the random pointer from origin node and the value is the new node for new list. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // old <-> new
        unordered_map<RandomListNode*, RandomListNode*> rel;
        RandomListNode* p = head;
        RandomListNode dummy {0};
        RandomListNode* res = &dummy;
        while (p) {
            if (rel.find(p) != rel.end()) {
                res->next = rel[p];
            } else {
                res->next = new RandomListNode {p->label};
            }

            if (p->random) {
                if (rel.find(p->random) == rel.end()) {
                    rel[p->random] = new RandomListNode {p->random->label};
                }
                res->next->random = rel[p->random];
            }

            p = p->next;
            res = res->next;
        }

        return dummy.next;
    }
};

Another interesting way of doing it w/o extra space can be accomplished by:

  1. first generate new list’s nodes and interleave with old list by using old node’s next pointer to pointer to new node. after this done, we get one single list with two lists’ nodes included and interleaved.
  2. repair new list nodes’ random pointer inplace.
  3. split two lists apart to restore the structure.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode* p = head;
        RandomListNode dummy {0};
        RandomListNode* res = &dummy;
        while (p) {
            auto* t = new RandomListNode {p->label};
            t->next = p->next;
            p->next = t;
            p = t->next;
        }

        p = head;
        while (p) {
            if (p->random)
                p->next->random = p->random->next;
            p = p->next->next;
        }

        p = head;
        if (p) { dummy.next = p->next; res = p->next; }
        while (p) {
            p->next = p->next->next;
            if (res->next) res->next = res->next->next;
            p = p->next;
            res = res->next;
        }

        return dummy.next;
    }
};

PS: if OJ allows me to modify the orignal list, then we can actually do it in two-pass without extra space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode* p = head;
        RandomListNode dummy {0};
        RandomListNode* res = &dummy;
        while (p) {
            res->next = new RandomListNode {p->label};
            res->next->random = p->random;

            auto* pp = p;
            p = p->next;
            pp->next = res->next;
            res = res->next;
        }

        res = dummy.next;
        while (res) {
            if (res->random) res->random = res->random->next;
            res = res->next;
        }
        return dummy.next;
    }
};

leetcode: Recover Binary Search Tree

The problam is fun. The note says

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

I first devise a way to detect mis-placed elements in one pass with a stack. the idea is quite simple after you thought through:

traverse the tree inorderly, the elements should appear in ascending order. the ones that disobey the rule are our spots.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    TreeNode* n1 = nullptr, *n2 = nullptr;
    void recoverTree(TreeNode *root) {
        if (!root) return;

        vector<TreeNode*> sp;
        TreeNode* nd = root, *prev = nullptr;
        while (sp.size() || nd) {
            while (nd) { sp.push_back(nd); nd = nd->left; }
            nd = sp.back(); sp.pop_back();
            if (n1 && n1->val < nd->val) break;

            if (prev && prev->val > nd->val) {
               if (!n1) {
                   n1 = prev;
                   n2 = nd;
               } else { n2 = nd; break; }
            }
            prev = nd;
            nd = nd->right;
        }

        std::swap(n1->val, n2->val);
    }
};

Then it is easy to trasfer the above into a O(1) space solution with morris inorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution2 {
public:
    TreeNode* n1 = nullptr, *n2 = nullptr;
    void recoverTree(TreeNode *root) {
        if (!root) return;

        TreeNode* prev = nullptr, *cur = nullptr;
        while (root) {
            if (!root->left) {
                prev = cur; cur = root;
                root = root->right;
            } else {
                auto* l = root->left;
                while (l->right && l->right != root) l = l->right;
                if (l->right == root) {
                    prev = cur; cur = root;
                    root = root->right;
                    l->right = nullptr;
                } else {
                    l->right = root;
                    root = root->left;
                }
            }
            if (prev && prev->val > cur->val) {
                if (!n1) { n1 = prev; n2 = cur; } 
                else { n2 = cur; }
            }
        }

        std::swap(n1->val, n2->val);
    }
};

PS: I found there is also a solution that first cleverly transforms the tree into an ordered linked-list and then detects the misplaced elements and then restore it back.

leetcode: Convert Sorted List to Binary Search Tree

If you have solved the previous problem, then it can be done by first convert the list into a vector and then do the same thing as the previous problem does. The interesting way is to do it on the list itself and almost O(1) space used.

The idea is thus:

  1. first, get length of the list
  2. recursively build left subtree bottom up
  3. create current root and move list pointer to next element
  4. recursively build right subtree bottom up
  5. return the root

My orignal solution uses an instance memeber ListNode* cur to remember current position of list. but I see some guys using reference to ListNode pointer to finish the job which I think more elegant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        int n = 0;
        ListNode* p = head;
        while (p) { n++; p = p->next; }
        return helper(head, n);
    }

    TreeNode* helper(ListNode* &h, int n) {
        if (n == 0) return nullptr;
        auto* left = helper(h, n/2);
        auto* root = new TreeNode {h->val};
        h = h->next;
        root->left = left;
        root->right = helper(h, n - n/2 - 1);
        return root;
    }
};

PS: I believe the space complexity is O(lgN) due to stack usage.

leetcode: triangle

This is also a problem which can be easily solved by dynamic programming (DP is so ubiquitous). Anyway, The Note said

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Well, acctually the problem can be solved without extra space. The idea is quit simple:
We store the dp value (current minimum path sum) in-place from the bottom up, then the value in the tip of triangle is the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {        
        int n = triangle.size();

        for (int l = n-2; l >= 0; l--) {
            auto& v = triangle[l];
            auto& v2 = triangle[l+1];
            for (int i = 0; i < v.size(); i++) {
                v[i] += min(v2[i], v2[i+1]);
            }
        }
        return triangle[0][0];
    }
};

leetcode: interleaving string

The description is here. The moment you see there are overlapping sub problems and sub optimal structure you know the problem can be solved easily using dynamical programming. The basic idea is thus:

the value of dp[i][j] represents if there is any of the interleaved strings come out of s1[0-i] and s2[0-j].

dp[i][j] = (dp[i-1][j] if s1[i] == s3[i+j]) or (dp[i][j-1] if s2[j] == s3[i+j])

for the sake of making programming easily, the matrix has been augmented by 1 in each dimension.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size(), len = s3.size();
        if (n + m != len) return false;

        std::vector<vector<int>> dp(n+1, std::vector<int>(m+1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) dp[i][0] = s1[i-1] == s3[i-1];
        for (int i = 1; i <= m; i++) dp[0][i] = s2[i-1] == s3[i-1];            

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                auto v1 = s1[i-1], v2 = s2[j-1], r2 = s3[i+j-1];
                if (v2 == r2) dp[i][j] = dp[i][j-1];
                if (!dp[i][j] && v1 == r2) dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][m];
    }
};

The above uses O(m*n) space, which is common case. We can reduce the space usage by the observation that to calculate dp[i][j] we only need to know dp[i-1][j] which is the value of last line above it and dp[i][j-1] which is the previous value of the same line.

So here I use array dp to represent both the values of the last line and the previous one. the trick is that when we calculating dp[j], dp[j-1] will store the previous value of the same line, and dp[j] itself (before write new value into it) is the value of last line above. Then we can use these two values to write new value into dp[j].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size(), len = s3.size();
        if (n + m != len) return false;

        std::vector<int> dp(m+1, true);
        for (int i = 1; i <= m; i++) dp[i] = s2[i-1] == s3[i-1];            

        for (int i = 1; i <= n; i++) {
            dp[0] = s1[i-1] == s3[i-1];
            for (int j = 1; j <= m; j++) {
                auto v1 = s1[i-1], v2 = s2[j-1], r2 = s3[i+j-1];
                auto old = dp[j];
                dp[j] = false;
                if (v2 == r2) dp[j] = dp[j-1];
                if (!dp[j] && v1 == r2) dp[j] = old; // the last line
                
            }
        }
        return dp[m];
    }
};

leetcode: largest rectangle in histogram

第一次遇到这个问题会觉得有难度，我是先做的maximal rectangle，然后再看到这个题，所以顺手就写了，结果TLE了。其实leetcode的时间复杂度要求还不是很变态的（想变态的就去spoj找虐），所以之前pass了就没在乎。现在回过头来做这个就不得不改变下写法。其实这个算法是我的maximal rectangle实现的基础。之前的写法有问题，因为在最坏情况下是O(n3)，但是基本思想是一样的。于是重写的时候做了改进。

基本思路是迭代height数组每一项，用栈sp记录到目前为止小于当前高度、并且高度递增的所有bar的位置。我们可以计算以栈中每一项为高度的最大矩形来找到目前为止的最大矩形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        std::vector<pair<int, int>> sp; // <height, index>
        int res = 0;
        sp.emplace_back(0, -1);
        for (int i = 0, n = height.size(); i < n; i++) {
            int k = height[i];
            bool dropping = false;
            while (sp.size() && sp.back().first >= k) {
                sp.pop_back();
                dropping = true;
            }
            sp.emplace_back(k, i);

            if (dropping || i == n-1 || (sp.back().first >= height[i+1])) {
                for (int p = 1; p < sp.size(); p++) {
                    auto r = sp[p].first * (i - sp[p-1].second);
                    res = max(r, res);
                }
            }            
        }

        return res;        
    }
};

基于同样的想法，我们可以稍微改写一下。由于我们只需要使用sp记录到当前位置为止所有上升的bar的高度，当遇到一个下降的bar时，所有栈里高度大于当前bar的位置在后面的计算中都不需要了，可以弹出并计算其最大矩形大小。整个算法用一个紧凑的while循环实现。这个方法保证了O(n)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int largestRectangleArea(vector<int> &height) {
    std::vector<pair<int, int>> sp; 
    int res = 0;
    height.push_back(0);
    sp.emplace_back(0, -1); // sentinal
    int i = 0;
    while (i < height.size()) {
        int k = height[i];
        if (sp.size() && sp.back().first <= k) {
            sp.emplace_back(k, i++);
        } else {
            auto p = sp.back();
            sp.pop_back();                
            res = max((i-sp.back().second-1) * p.first,  res);
        }
    }

    while (sp.size() > 1) {
        auto p = sp.back();
        sp.pop_back();                
        res = max((i-sp.back().second-1) * p.first,  res);            
    }
    return res;        
}

最后一个方法据说是经典实现，它基于segment tree来实现，O(nlgn)的时间复杂度。segment tree的思想可以看这个链接，实现比较容易。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class SegmentTree {
public:
    std::vector<int> nodes;
    int n;

    SegmentTree(const vector<int>& v) {
        n = v.size();
        int h = std::ceil(std::log2(n)); 
        nodes = std::vector<int>(2*std::pow(2,h)-1, 0);

        build(v, 0, 0, n-1);        
    }

    int query(const vector<int>& v, int ql, int qr) const {
        return queryMin(v, 0, 0, n-1, ql, qr);
    }

private:
    int idOfMin(const vector<int>& v, int id1, int id2) const {
        if (id1 == INT_MAX) return id2;
        else if (id2 == INT_MAX) return id1;

        return (v[id1] < v[id2]) ? id1 : id2;
    }

    // [l, r] is region of id, [ql, qr] is query region
    int queryMin(const vector<int>& v, int id, int l, int r, int ql, int qr) const {
        if (ql <= l && qr >= r) return nodes[id];
        if (ql > r || qr < l) return INT_MAX;

        int mid = l + (r - l) / 2;
        return idOfMin(v, queryMin(v, id*2+1, l, mid, ql, qr), queryMin(v, id*2+2, mid+1, r, ql, qr));
    }

    int build(const vector<int>& v, int id, int l, int r) {
        if (l == r) {
            return nodes[id] = l;
        }

        int mid = l + (r-l)/2;
        return nodes[id] = idOfMin(v, build(v, id*2+1, l, mid), build(v, id*2+2, mid+1, r));
    }

};

class Solution3 {
public:
    int largestRectangleArea(vector<int> &height) {
        if (height.size() == 0) return 0;
        SegmentTree st(height);
        return dac(height, st, 0, height.size()-1);
    }

    int dac(const vector<int>& height, const SegmentTree& st, int l, int r) {
        if (l > r) return -1;
        if (l == r) return height[l];
        int id = st.query(height, l, r);
        return max(max(dac(height, st, l, id-1), dac(height, st, id+1, r)), (r-l+1)*height[id]);
    }
};