sliding_window_maximum

hitzzc · hitzzc · commit 1cc60e30b86e · 2016-10-19T13:13:58.000+08:00
diff --git a/README.md b/README.md
@@ -194,6 +194,8 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [236. Lowest Common Ancestor of a Binary Tree](https://github.com/hitzzc/go-leetcode/tree/master/lowest_common_ancestor_of_a_binary_tree)
 #### [237. Delete Node in a Linked List](https://github.com/hitzzc/go-leetcode/tree/master/delete_node_in_a_linked_list)
 #### [238. product of array except self](https://github.com/hitzzc/go-leetcode/tree/master/product_of_array_except_self)
+#### [239. Sliding Window Maximum](https://github.com/hitzzc/go-leetcode/tree/master/sliding_window_maximum)
+
 
 
 
diff --git a/sliding_window_maximum/sliding_window_maximum.go b/sliding_window_maximum/sliding_window_maximum.go
@@ -0,0 +1,19 @@
+package sliding_window_maximum
+
+func maxSlidingWindow(nums []int, k int) []int {
+	ret := []int{}
+	idxArray := []int{}
+	for i := range nums {
+		for len(idxArray) != 0 && idxArray[0] <= i-k {
+			idxArray = idxArray[1:]
+		}
+		j := len(idxArray) - 1
+		for ; j >= 0 && nums[idxArray[j]] <= nums[i]; j-- {
+		}
+		idxArray = append(idxArray[:j+1], i)
+		if i >= k-1 {
+			ret = append(ret, nums[idxArray[0]])
+		}
+	}
+	return ret
+}
