走吧，去血洗Indeed

楼主请问python validation那题，为什么用stack复杂度会优于brute force呢？我的brute force思路是用个list存，然后每一次来新的line跟preLine做比较，我觉的复杂度跟stack一样 都是O(N) 吧，这是我不用stack和用stack的代码：

1. private static boolean validate(String[] lines) {
   
2.                 List<String> list = new ArrayList<String>();
   
3.                 for(String line : lines) {
   
4.                         int tab = getTab(line);
   
5.                         if(list.size() == 0 && tab != 0) {
   
6.                                 System.out.println(line);
   
7.                                 return false;
   
8.                         }
   
9.                        
   
10.                         if(tab == 0 && list.size() == 0) {
    
11.                                 list.add(line);
    
12.                         }else {
    
13.                                 String preLine = list.get(list.size() - 1);
    
14.                                 int preTab = getTab(preLine);
    
15. 
    
16.                                 if (isControl(preLine)) {
    
17.                                         if (tab != preTab + 1) {
    
18.                                                 System.out.println(line);
    
19.                                                 return false;
    
20.                                         } else {
    
21.                                                 list.add(line);
    
22.                                         }
    
23.                                 } else {
    
24.                                         if (tab > preTab) {
    
25.                                                 System.out.println(line);
    
26.                                                 return false;
    
27.                                         } else {
    
28.                                                 list.add(line);
    
29.                                         }
    
30.                                 }
    
31.                         }
    
32.                 }
    
33. 
    
34.                 return true;
    
35.         }
    
36. 
    

复制代码

1. public static boolean validateStack(String[] lines){
   
2.         //就用stack来存之前的line就行
   
3.         Stack<String> stack = new Stack<>();
   
4.                 for (String line : lines) {
   
5.                         int tab = getTab(line);
   
6.                        
   
7.                         if (stack.isEmpty()) {// 先检查是不是第一行
   
8.                                 if (tab != 0) {
   
9.                                         System.out.println(line);
   
10.                                         return false;
    
11.                                 }
    
12.                         } else if (isControl(stack.peek())) {// 再检查上一行是不是control statement
    
13.                                 if (getTab(stack.peek()) + 1 != tab) {
    
14.                                         System.out.println(line);
    
15.                                         return false;
    
16.                                 }
    
17.                         } else {
    
18.                                 while (!stack.isEmpty() && getTab(stack.peek()) > tab) {
    
19.                                         stack.pop();
    
20.                                 }
    
21.                                 if (getTab(stack.peek()) != tab) {
    
22.                                         System.out.println(line);
    
23.                                         return false;
    
24.                                 }
    
25.                         }
    
26.                         stack.push(line);
    
27.                 }
    
28.         return true;
    
29.     }

复制代码

没权限下载附件+1 这是为什么