CSS选择器从右向左的匹配规则
下面这个栗子，CSS选择器它是如何工作的？
.mod-nav h3 span {font-size: 16px;}
如果不知道匹配规则，可能的理解是从左向右匹配:先找到.mod-nav，然后逐级匹配h3、span，在这个过程中如果遍历到叶子节点都没有匹配就需要回溯，继续寻找下一个分支。
但事实上，CSS选择器的读取顺序是从右向左。
还是上面的选择器，它的读取顺序变成：先找到所有的span，沿着span的父元素查找h3，中途找到了符合匹配规则的节点就加入结果集；如果直到根元素html都没有匹配，则不再遍历这条路径，从下一个span开始重复这个过程（如果有多个最右节点为span的话）。
在某条CSS规则下（比如.mod-nav h3 span），会形成一条符合规则的索引树，树由上至下的节点是规则中从右向左的一个个选择符匹配的节点。索引树遍历的具体过程可以看寒冬大大的一段视频。
为什么从右向左的规则要比从左向右的高效？
假如DOM的结构如上图，匹配规则是.mod-nav h3 span。
若从左向右的匹配，过程是：从.mod-nav开始，遍历子节点header和子节点div，然后各自向子节点遍历。在右侧div的分支中，最后遍历到叶子节点a，发现不符合规则，需要回溯到ul节点，再遍历下一个li-a，假如有1000个li，则这1000次的遍历与回溯会损失很多性能。
再看看从右至左的匹配：先找到所有的最右节点span，对于每一个span，向上寻找节点h3，由h3再向上寻找class=mod-nav的节点，最后找到根元素html则结束这个分支的遍历。
很明显，两种匹配规则的性能差别很大。之所以会差别很大，是因为从右向左的匹配在第一步就筛选掉了大量的不符合条件的最右节点（叶子节点）；而从左向右的匹配规则的性能都浪费在了失败的查找上面。
当然这是比较明显情况，如果在叶子上存在多个不符合条件的span，从右向左的规则也会走一些弯路（这时就需要优化CSS选择器了）。但平均来说它还是更高效，因为大多时候，一个DOM树中，符合匹配条件的节点（如.mod-nav h3 span）远远远远少于不符合条件的节点。
jQuery从1.3版本开始使用的Sizzle引擎，它按照了CSS选择器的匹配规则（从右至左）进行DOM元素的查找与匹配（当然其中做了很多优化），性能得到了很大的提升。
欢迎批评指正。
[创新工场2014] 2014创新工场校园招聘笔试题
继上一篇博文《[创新工厂2014]回文修复》后，继续推出第二道创新工厂的笔试算法题~
对于非负数列a1、a2、......、an，在数轴上做垂线连接点(i,0)和(i,ai)。选择这样的两条线和x轴可以形成一个容器，我们以面积代表所装的水，求以这种方式构成的容器能装的最大面积。比如选择a2=3、a5=6，则所装的面积为9。
分析：
这道题实际上的意思是：对于一个给定的序列，求abs(i-j)*min(a[i],a[j])的最大值！
先对序列按照高度排序，然后按照排序后的顺序进行枚举，枚举过的就做标记，表示已经访问过了，保证了当前的节点，是序列里的最小高度的板，那么以这个板为边界能装的最大的水，肯定就是当前序列的最左边，或者最右边，因为没有其他板比当前板更矮了，分别计算，并且update最大值。
如果当前这个节点就是边界，且已经访问过(即比当前的节点的高度更小)，那么就要对L和R进行收缩，保证L和R是当前节点能构成最大容器的最远边界。
代码如下：
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <limits.h>
using namespace std;
#define max(a,b) a>b?a:b
typedef struct Pair{
int i;
int ai;
}Pair;
Pair p[101];
int n;
int flag[101];
bool cmp(Pair a,Pair b)
{
if(a.ai<b.ai)
return true;
else
return false;
}
int main()
{
freopen("b3.in","r",stdin);
freopen("b3.out","w",stdout);
int maxRes;
int L,R;
while(scanf("%d",&n)!=EOF)
{
memset(flag,0,sizeof(flag));
maxRes = INT_MIN;
for(int i=0; i<n; i++)
{
scanf("%d",&p[i].ai);
p[i].i = i;
}
sort(p,p+n,cmp);
L=0;
R=n-1;
for(int i=0; i<n; i++)
{
flag[p[i].i] = 1;
maxRes = max(maxRes,abs(L-p[i].i)*p[i].ai);
maxRes = max(maxRes,abs(R-p[i].i)*p[i].ai);
if(p[i].i==L)
{
while(flag[L]==1) L++;
}
if(p[i].i==R)
{
while(flag[R]==1) R--;
}
}
printf("%d\n",maxRes);
}
return 0;
}
如果有错误的地方，还望大家及时指出，谢谢~