ספט.05

יש לממש מחסנית מינימום ומקסימום (Min / Max Stack)

יש לממש מחסנית מינימום ומקסימום (Min / Max Stack)

יש לממש מחסנית מינימום ומקסימום (Min / Max Stack) פונקציה צריכה להחזיר תוצאה ב O(1)

  1. //one implementation used dictionary
  2. public class MinMaxStack {
  3. List<Dictionary<string, int>> minMaxStack = new List<Dictionary<string, int>>();
  4. List<int> stack = new List<int>();
  5. public int Peek() {
  6. return stack[stack.Count - 1];
  7. }
  8.  
  9. public int Pop() {
  10. minMaxStack.RemoveAt(minMaxStack.Count - 1);
  11. var val = stack[stack.Count - 1];
  12. stack.RemoveAt(stack.Count - 1);
  13. return val;
  14. }
  15.  
  16. public void Push(int number) {
  17. Dictionary<string, int> newMinMax = new Dictionary<string, int>();
  18. newMinMax.Add("min", number);
  19. newMinMax.Add("max", number);
  20. if(minMaxStack.Count > 0) {
  21. Dictionary<string, int> lastMinMax = new Dictionary<string, int> (minMaxStack[minMaxStack.Count - 1]);
  22. newMinMax["min"] = Math.Min(lastMinMax["min"], number);
  23. newMinMax["max"] = Math.Max(lastMinMax["max"], number);
  24. }
  25. minMaxStack.Add(newMinMax);
  26. stack.Add(number);
  27. }
  28.  
  29.  
  30. public int GetMin() {
  31. return minMaxStack[minMaxStack.Count - 1]["min"];
  32. }
  33.  
  34. public int GetMax() {
  35. return minMaxStack[minMaxStack.Count - 1]["max"];
  36. }
  37. }
  38.  
  39. //other implementation - used 2 variables + additional values in stack
  40. public class MinMaxStack {
  41. int max = Int32.MinValue;
  42. int min = Int32.MaxValue;
  43. Stack<int> stack = new Stack<int>();
  44. public int Peek() {
  45. return stack.Peek();
  46. }
  47.  
  48. public int Pop() {
  49. int value = stack.Pop();
  50. if(stack.Count <=2 ) {
  51. max = Int32.MinValue;
  52. min = Int32.MaxValue;
  53. stack = new Stack<int>();
  54. } else {
  55. if (value == min)
  56. min = stack.Pop();
  57. if (value == max)
  58. max = stack.Pop();
  59. }
  60. return value;
  61. }
  62.  
  63. public void Push(int number) {
  64. if(number <= min) {
  65. stack.Push(min);
  66. min = number;
  67. }
  68. if(number >= max) {
  69. stack.Push(max);
  70. max = number;
  71. }
  72. stack.Push(number);
  73. }
  74.  
  75. public int GetMin() {
  76. return min;
  77. }
  78.  
  79. public int GetMax() {
  80. return max;
  81. }
  82. }


תגיות:
שתף את הסיפור הזה:

תגובות(1)

  1. רחל גבירץ
    לפני פחות משנה
    תקשיבי הרבה מאד זמן שלא מצאתי מישהי אלופה כמוך באמת כולי הערכה שאלות מסודרות תשובות מעניניות ממש תודה רבה 

השאירו תגובה

קפטצ'ה לא מתאימה

תגובה