ホームページ >Java >&#&チュートリアル >Javaで単調スタックを使用する方法
この質問では、より暴力的なものを選択してください。解決 。
まず結果を保存するために nums と同じ長さの res 配列を初期化し、nums の値を取り出し、nums2[j] == nums が見つかるまで nums2 を検索します。 [i]. 次に、nums2 の j からトラバースして、nums[i] より大きい配列を見つけて返します。見つからない場合は、-1.
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[] res = new int[m]; for (int i = 0; i < m; ++i) { int j = 0; while (j < n && nums2[j] != nums1[i]) { ++j; } int k = j + 1; while (k < n && nums2[k] < nums2[j]) { ++k; } res[i] = k < n ? nums2[k] : -1; } return res; } }#を返します。 ## 2. 毎日の温度質問の説明 アイデアの詳細な説明この質問比較的暴力的な手法も用いられます。前の質問と同じです。 二重ループ。明らかに、この方法の時間計算量は高くなります。時間の複雑さがより低い方法もここで提供されます。 モノトーン スタック私たちが維持しているのは、結果の配列であるギャップ配列です。まずスタックを作成し、スタックが空かどうかを確認します。空の場合は、スタックを直接プッシュします。スタック。空でない場合は比較します。スタックの最上位要素と現在の要素の差。現在の要素が現在の要素より大きい場合、差分は対応する結果配列とスタックの最上位要素に入れられます。現在の要素が結果の配列より小さい場合、スタックにプッシュされます。 ここにアニメーションへのリンクがあります。アニメーションで単調なスタックを学ぶことをお勧めします。 コードと結果
class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] answer = new int[temperatures.length]; for(int i = 0 ; i < temperatures.length ; i++){ int res = 0; for(int j = i+1 ; j < temperatures.length; j++){ res++; if(temperatures[j] > temperatures[i]){ answer[i] = res; break; } } } return answer; } }
アイデアの詳細な説明この質問のアイデアは単調スタックです。質問 1 は総当たりの解決策です。この質問では単調スタックの使用が必要です。 原理は2番目の質問の方法と同じで、ループに注目するだけです。コードに直接アクセスします。よくわからない場合は、2 番目の質問のビデオを見てから、これを参照してください。 コードと結果
class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] ret = new int[n]; Arrays.fill(ret, -1); Deque<Integer> stack = new LinkedList<Integer>(); for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次,只需要2*n-1就够用了 while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) { ret[stack.pop()] = nums[i % n]; } stack.push(i % n);//利用取模来进行循环也是一种常用的方法 } return ret; } }
以上がJavaで単調スタックを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。