Break algorithm --- map

---

---

---

Resource reference ：
LeetCode
Chinese version ：https://leetcode-cn.com/problemset/all/
English version ：https://leetcode.com/problemset/all/

Related code implementation – python Language ：
https://github.com/muxintong/break-algorithm/

LeetCode Problem solving summary
https://github.com/labuladong/fucking-algorithm
https://labuladong.gitee.io/algo/
https://grandyang.com/leetcode/1147/

Python3 file
https://docs.python.org/3/

data structure
https://www.runoob.com/data-structures/
Problem Solving with Algorithms and Data Structures using Python
https://runestone.academy/runestone/books/published/pythonds/index.html

---

---

---

One . Monotonic stack

• 1.1 Introduction to monotone stack
• 1.2 On behalf of the topic
  • 1.2.1 Daily temperature （739）
  • 1.2.2 Remove duplicate letters （316）
  • 1.2.3 Maximum sliding window （239_ difficult _O（n） Time complexity resolution ）
  • 1.2.4 The largest rectangle （85）
  • 1.2.5 Next bigger element II（503）
  • 1.2.6 The largest rectangle in the histogram （84_ difficult ）
  • 1.2.7 Rainwater collection （42_ difficult _ Performance sensitive ）
  • 1.2.8 Stock price span （901）

Two . Union checking set

• 2.1 And look up the introduction
• 2.2 On behalf of the topic
  • 2.2.1 Circle of friends （547）
  • 2.2.2 Redundant connections （684）
  • 2.2.3 Number of Islands （200_ Must do ）
  • 2.2.4 Sentence similarity II (737_ members )
  • 2.2.5 The path with the highest score （1102_ members ）
  • 2.2.6 Connect all cities at the lowest cost （1135_ members ）
  • 2.2.7 Distinguish trees by pictures （261_ members ）
  • 2.2.8 The smallest equivalent string in lexicographic order （1061_ members ）
  • 2.2.9 The number of connected components in an undirected graph （323_ members ）
  • 2.2.10 Minimize the spread of malware （924_ difficult ）

3、 ... and . The sliding window

• 3.1 Slide window Introduction
• 3.2 On behalf of the topic
  • 3.2.1 Make strings equal as much as possible （1208）
  • 3.2.2 Subarray with the smallest length （209）
  • 3.2.3 Longest substring without repeating characters （3）
  • 3.2.4 Maximum continuous 1 The number of III (1004)
  • 3.2.5 At most K Longest substring of different characters （340_ members _ difficult ）
  • 3.2.6 The minimum number of exchanges to combine all 1（1151_ members ）
  • 3.2.7 The longest substring containing at most two different characters （159_ members ）
  • 3.2.8 The length is K There is no repetition in the string （1100_ members ）
  • 3.2.9 Minimum cover substring （76）
  • 3.2.10 String arrangement （567）
  • 3.2.11 Look for all the letter ectopic words （438）

Four . The prefix and & HASH

• 4.1 The prefix and & HASH Introduce
• 4.2 On behalf of the topic
  • 4.2.1 And for K Subarray （560）
  • 4.2.2 Continuous subarrays and （523）
  • 4.2.3 And can be K A subarray of integers （974）

5、 ... and . Difference

• 5.1 Difference
• 5.2 On behalf of the topic
  • 5.2.1 Carpooling （1094）
  • 5.2.2 Flight booking Statistics （1109）
  • 5.2.3 The best time to buy and sell stocks （121_ Simple ）
  • 5.2.4 The best time to buy and sell stocks II（122）
  • 5.2.5 Conference Room II （253_ members ）
  • 5.2.6 Division of arithmetic sequence （413）

6、 ... and . A topological sort

• 6.1 Introduction to topological sorting
• 6.2 On behalf of the topic
  • 6.2.1 The curriculum II（610）
  • 6.2.2 Sequence reconstruction （444_ members ）
  • 6.2.3 Mars Dictionary （269）

7、 ... and . character string

• 7.1 The prefix and & HASH Introduce
• 7.2 On behalf of the topic
  • 7.2.1 Longest text substring （5）
  • 7.2.2 Restore IP Address （93-dfs）
  • 7.2.3 String multiplication （43）
  • 7.2.4 Basic calculator II（227）

8、 ... and .BFS

• 8.1 BFS Introduce
• 8.2 On behalf of the topic
  • 8.2.1 The word chain （127）
  • 8.2.2 Word splitting （139）
  • 8.2.3 The surrounding area （130）
  • 8.2.4 The nearest distance to the building （317）
  • 8.2.5 maze II （505_ members ）
  • 8.2.6 The Minesweeper game （529）
  • 8.2.7 tuixiangzi （1263）
  • 8.2.8 The attacking Knight （1197_ members ）
  • 8.2.9 Bus routes （815）
  • 8.2.10 The shortest bridge （934）

Nine .DFS

• 9.1 DFS Introduce
• 9.2 On behalf of the topic
  • 9.2.1 The shortest bridge （934）
  • 9.2.2 The path with the highest score （1102_ members ）
  • 9.2.3 Redundant connections II（685）
  • 9.2.4 Lonely pixels I（531_ members ）
  • 9.2.5 Lonely pixels II （533_ members ）
  • 9.2.6 Rescheduling （332）
  • 9.2.7 raid homes and plunder houses III（337）
  • 9.2.8 The sum of the paths II（113）

Ten . Dynamic programming

• 10.1 Introduction to dynamic planning
• 10.2 On behalf of the topic
  • 10.2.1 raid homes and plunder houses II（213）
  • 10.2.2 Separate the arrays to get the maximum and （1043）
  • 10.2.3 To divide into equal and subsets （416）
  • 10.2.4 The best time to buy and sell stocks III（123）
  • 10.2.5 Different paths （62）
  • 10.2.6 Different paths II （63）
  • 10.2.7 4 Key keyboard （651_ members ）
  • 10.2.8 Bombing the enemy （361）
  • 10.2.9 School bike Distribution II（1066_ members ）
  • 10.2.10 The number of corner rectangles （750_ members ）
  • 10.2.11 Toss a coin （1230）
  • 10.2.12 The shortest path to form a string （1055_ members ）

11、 ... and . Greedy Algorithm

• 11.1 Introduction to greedy algorithm
• 11.2 On behalf of the topic
  • 11.2.1 Detonate the balloon with a minimum number of arrows （452）
  • 11.2.2 Share the chocolate （1231_ members ）
  • 11.2.3 Exchanging characters makes the string the same （1247）
  • 11.2.4 Jumping game II（45）
  • 11.2.5 Task scheduler （621）
  • 11.2.6 Swing sequence （376）

Twelve . Dictionary tree

• 12.1 Introduction to dictionary tree
• 12.2 On behalf of the topic
  • 12.2.1 Compression coding of words （820）
  • 12.2.2 Share the chocolate （1231_ members ）
  • 12.2.3 Word substitution （648）
  • 12.2.4 Realization Trie ( Prefix tree )（208）

---

---

---

---

One . Monotonic stack

1.1 Introduction to monotone stack

Monotonic stack ：

1. Definition ： A stack in which elements are monotonically increasing or decreasing , Monotone stack can only operate at the top of the stack .
   Monotonic stack = monotonous + Stack , Therefore, it meets two characteristics at the same time : monotonicity 、 The characteristics of the stack .
   monotonicity : The data stored in the monotone stack is orderly ( Monotonically increasing or decreasing ).
   Stack : Last in, first out .
2. Realization ： The elements in a monotone stack are monotonous , Before the element is added to the stack , At the top of the stack, the elements that break the monotony of the stack are deleted .
   Monotonically decreasing stacks ： Find the first element larger than the current element from the left

	stack<int> st;
	for ( Traverse the array )
	{
    
		if ( The stack is empty  ||  The stack top element is greater than or equal to the current comparison element )
		{
    
			 Push ;
		}
		else
		{
    
			while ( Stack is not empty.  &&  The stack top element is smaller than the current element )
			{
    
				 Stack top element out of stack ;
				 Update results ;
			}
			 Current data stack ;
		}
	}

The above code optimization merge ：

stack<int> st;
for( Traversal array ）{
    
	while（ The current element  >  Top element of stack  &&  The stack is not empty ）{
    
		 Bomb stack ;//catch it！ Found the first element larger than the current element from the left ！
		 Update result set ;
	}
	 The current element is put on the stack ;
}

Monotonically increasing stacks ： Find the first element smaller than the current element from the left

stack<int> st;
for(int i=0; i<arr.length; i++){
    
	while( The current element  <  Top element of stack  &&  The stack is not empty ）{
    
		 Bomb stack ;//catch it！ Found the first element smaller than the current element from the left ！
		 Update result set ;
	}
	 The current element is put on the stack ;
}

3. Time complexity ：O(n)
   linear , Each element is traversed once .
   Because it satisfies monotonicity and each number will only be put on the stack once , And they will never enter the stack again after they are out of the stack , So we can reduce the time complexity O(n) Solve some problems in the case of .
4. application ：
   - Monotonically increasing stack can be found from left first Elements smaller than the current number
   - Monotonic decreasing stack can be found from left first Elements larger than the current number