This challenge is not difficult; however, I make a mistake when analyzing the time complexity. The reason is that I make a large duplicate and useless calculation in my solution. Take a look into the detail for the challenge “Longest Peak”. Writeup You can see the detail of challenge and my initial solution in this video. However, I can finish this problem in O(n) in fact. Why? Assume there is ten numbers in array:

First, I need to come up with the words, ‘Damn it’. This belongs to my LeetCode Self Challenge for 30 mins. I almost finish the problem, but I forget to check the search space for binary search, which should be the common sense for it. I will provide the writeup and the optimization here. Writeup The programming language in video is C++ 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 int search(vector<int>& nums, int target) { if(nums.

查找一個數組裡面的目標，我們能夠想到最快的方法可能是hash table，然而當數組很大時，內存就會爆掉！第二個選擇則是binary search。Binary search的觀念看似很簡單，然而卻有多種實現方法！最近在做一些題目時(包括面試時)發現binary search的應用面其實很廣，只要dataset有單調性，我們都可以用binary search把時間複雜度縮小到對數等級。特別感謝Leetcode出了Explore篇章幫助我進行摸索。下面我也會針對Explore上的題目做出解析來整理Binary search的訣竅！ 解題過程 所有的元素為unique，尋找唯一的index Explore Binary Search 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int search(vector<int>& nums, int target) { if(target < -9999 || target > 9999) return -1; int start = 0, end = nums.size() - 1, mid = 0; while(start <= end) { mid = start + ((end - start) >> 1); // remember your bracket if(nums[mid] == target) return mid; if(nums[mid] < target) start = mid + 1; else end = mid - 1; } return -1; } }; 以上我的解法只有哪到66%的成績，但在我審了一遍前段的code之後，我推斷時間複雜度只差在I/O優化！

UVa 105 - The Skyline Problem This problem tests the application of priority queue which is implemented with min-heap. Min-heap takes O(logn) to insert a new node. It takes O(1) to extract current minimum value and O(logn) to sort again. With this data structure, I can iterate the boundaries of building in ascending order. My idea is recording all boundaries and associated heights in priority queue and current existing height in multiset.

I use modified-BST to solve this problem. Each time inserting a new node takes O(logn) and also updates the value of count, and there are n nodes; therefore, I think the time complexity of my solution is O(nlogn). Writeup The programming language in video is C++ For the source code in video: Github Conclusion Order of input: left to right or right to left? Definition of node: what member should we define for each nodes in tree?

State machine is common and useful technique to be used in algorithm. I really recommend you to figure the last solution out thoroughly. Then try my extended problem! Writeup The programming language in video is C++ For the source code in video: Github Conclusion Solution 1 and 2 are similiar to each other, and they both try using 3*n + 1 to separate the single number from the others.